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

---

在这个问题中，我们需要通过将bin1字符串的第二个字符替换为bin1字符串的第一个和第二个字符的最小值或最大值，然后移除第一个字符，来将bin1字符串转换为bin2字符串。

由于我们需要移除第一个字符，我们需要确保两个字符串的最后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 <bits/stdc++.h>
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) ，因为我们没有使用任何动态空间。

我们学习了如何通过执行给定的操作将第一个二进制字符串转换为第二个二进制字符串。程序员可以尝试解决这个问题，以检查是否可以通过将倒数第二个字符替换为最后一个和倒数第二个字符的最小值或最大值，然后移除最后一个字符来将一个字符串转换为另一个字符串。