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

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

我們學會了按照給定的操作將第一個二進位字串轉換為第二個二進位字串。程式設計師可能會嘗試透過用最後一個和最後第二個字元的最小值或最大值替換最後一個字元並刪除最後一個字元來檢查一個字串是否可以轉換為另一個字串。

以上是透過重複替換第二位，使二進位字串相等的詳細內容。更多資訊請關注PHP中文網其他相關文章！