透過重複替換第二位使二進位制字串相等

---

在這個問題中，我們需要透過將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) ，因為我們沒有使用任何動態空間。

我們學習瞭如何透過執行給定的操作將第一個二進位制字串轉換為第二個二進位制字串。程式設計師可以嘗試解決這個問題，以檢查是否可以透過將倒數第二個字元替換為最後一個和倒數第二個字元的最小值或最大值，然後移除最後一個字元來將一個字串轉換為另一個字串。