通过重复替换第二位，使二进制字符串相等

在这个问题中，我们需要将 bin1 字符串转换为 bin2 字符串，方法是将 bin1 字符串的第二个字符替换为第一个和第二个字符中的最小值或最大值，并删除第一个字符。

由于我们需要删除首字符，因此需要确保两个字符串中最后一个 len2 − 1 字符相同。另外，我们需要确保通过对 bin1 字符串的起始字符执行给定的操作，可以获取第二个字符串的第一个字符。

问题陈述 - 我们分别给出了 len1 和 len2 长度的 bin1 和 bin2 二进制字符串。我们需要检查是否可以通过以下操作将 bin1 字符串转换为 bin2 字符串。

• 使用 bin1 字符串的第一个和第二个字符中的最小值或最大值更新 bin1 字符串的第二个字符。

• 去掉bin1字符串的第一个字符，每次操作字符串大小都会减少1。

示例

输入

红墨

一站式小红书图文生成器

下载

bin1 = "0101011"; bin2 = "011";

输出

Yes

说明- 我们可以执行以下操作将 bin1 字符串转换为 bin2 字符串。

• 我们可以用 min(0,1) 替换第二个字符并删除第一个字符。因此，该字符串变为 001011。

• 我们再次执行相同的操作，字符串变为01011。

• 在接下来的几次操作中，字符串分别变为 0011 和 011。

输入

bin1 = "1110"; bin2 = "1110";

输出

Yes

解释 - 给定的字符串已经相同。

输入

bin1 = "101101"; bin2 = "1110";

输出

No

说明 - 我们无法通过执行给定的操作将 bin1 字符串转换为 bin2 字符串。

方法 1

如果 bin1 字符串的长度较小，我们无法将其转换为 bin2 字符串。

在其他情况下，bin1 字符串的最后一个 len2 − 1 字符保持不变，因为我们不对它执行任何操作。因此，两个字符串中的最后 len2 − 1 个字符应该相同。

另外，如果bin2字符串的第一个字符是‘0’，我们应该对bin1字符串的起始字符进行min()操作，并且它应该至少包含一个‘0’。

如果bin2字符串中的第一个字符是‘1’，我们应该对bin2字符串的起始字符进行max()操作，并且它应该至少包含一个‘1’。

算法

步骤 1 - 如果 bin1 的长度小于 bin2 字符串的长度，则返回 false。

步骤 2 - 从第二个位置开始遍历 bin2 字符串。

步骤 3 - 如果 bin2[p] 不等于 bin1[p + len1 - len2]，则返回 false，因为最后 len2 -1 个字符不相同。

步骤4 - 遍历第一个len1 - len2 + 1个字符，检查是否包含bin2[0]字符。如果是，则返回true。

第 5 步 - 在函数末尾返回 false。

示例

#include 
using namespace std;

bool convertAtoB(string bin1, string bin2) {
    int len1 = bin1.size(), len2 = bin2.size();
    // When length 1 is less than length 2
    if (len1 < len2) {
        return false;
    }
    // Check whether substring bin1[p + len1 - len2]... bin1[len1] and bin2[1]... bin2[len2]
    for (int p = 1; p < len2; p++) {
        if (bin1[p + len1 - len2] != bin2[p]) {
            return false;
        }
    }
    // Check whether substring bin1[0... len1 - len2 - 1] contains bin2[0]
    for (int p = 0; p < len1 - len2 + 1; p++) {
        if (bin1[p] == bin2[0]) {
            return true;
        }
    }
    return false;
}
int main() {
    string bin1 = "0101011";
    string bin2 = "011";
    bool res = convertAtoB(bin1, bin2);
    if (res == true) {
        cout << "YES, It is possible to convert bin1 to bin2.";
    } else {
        cout << "NO, It is not possible to convert bin1 to bin2.";
    }
}

输出

YES, It is possible to convert bin1 to bin2.

时间复杂度 - O(N) 来匹配字符串字符。

空间复杂度 - O(1)，因为我们不使用任何动态空间。

我们学会了按照给定的操作将第一个二进制字符串转换为第二个二进制字符串。程序员可能会尝试通过用最后一个和最后第二个字符的最小值或最大值替换最后一个字符并删除最后一个字符来检查一个字符串是否可以转换为另一个字符串。