將二進位制字串透過翻轉字首轉換為另一個字串，並使翻轉次數最少

---

字首是從第零個索引開始的子字串，其長度可以是 1 到給定字串長度的任何值。我們得到了兩個二進位制字串，這意味著這兩個字串僅包含兩種不同的字元，我們需要透過翻轉字首將第一個字串轉換為第二個字串，並使翻轉次數最少。此外，還給定這兩個字串的長度相等。

輸入 1

string str1 = "01100"
string str2 = "10101" 

輸出

3

解釋

我們唯一可以執行的操作是選擇任意長度的字首，然後更新其值。因此，我們可以選擇整個字串，則字串將變為 10011。現在，我們可以選擇長度為字串總長度減 1 的字首，則字串將變為 01101。最後，我們可以選擇長度為 2 的字首，這將給我們答案。

輸入 2

 string str1 = “1001” 
 string str2 = “1000” 
    

輸出

2

思路

我們可以在這裡觀察到，如果我們需要透過翻轉所選字首的所有字元來更改字串。

需要注意的是，如果我們想更改第一個字串的最後一位，則必須選擇整個字串，然後以後就不需要再選擇整個字串了。

因此，根據這個觀察結果，我們可以從最後一位遍歷字串，並檢查兩個字串的當前字元是否相同。如果它們相同，則我們移動到下一個字元，否則我們將更新答案並翻轉字串。

現在，翻轉整個字串是一個代價較高的步驟，因此與其翻轉整個字串，不如使用一個變數來標記字串是否被翻轉。

如果字串翻轉一次，則字元將發生變化，但如果我們翻轉字串兩次，則字串將恢復到相同的形式。

程式碼實現步驟

• 首先，我們將建立一個主函式，並定義字串，並呼叫函式以獲取所需的最小步驟數。

• 我們的輔助函式將把兩個字串作為引數，並返回一個整數，該整數將是我們所需的數字。

• 在函式中，我們將獲取字串的長度並將其儲存在一個變數中。

• 將有一個布林變數來儲存當前字串是否被翻轉。

• 我們將使用 for 迴圈從最後一個索引到第零個索引遍歷字串。

• 如果兩個字串的當前字元相同且字串被翻轉，或者字元不同且字串未被翻轉，則我們將答案更新為 1 並翻轉字串。

• 最後，我們將返回答案值，並在主函式中列印它。

示例

#include <bits/stdc++.h>
using namespace std;
// creating a function to find number of steps required 
int stepsReq(string str1, string str2){
   int len = str1.length(); // getting length of the strings
   int ans = 0; // variable to store the answer 
   bool isFlipped = false;
   // traversing over the string 
   for(int i=len-1; i>=0; i--){
      if(str1[i] == str2[i]){
         if(isFlipped){
            // characters are the same but the string is flipped ans++;
            isFlipped = false;
         }
       } else{
          if(!isFlipped){
             // characters are not the same and the string is not flipped 
             isFlipped = true;
             ans++;
          }
       }
   }
   return ans; // return the answer 
}
int main(){
   string str1 = "01100"; // given strings 
   string str2 = "10101";
   // calling the function 
   cout<<"The minimum number of steps required to convert the first string to another by flipping the prefixes is" <<stepsReq(str1,str2)<<endl;
   return 0; 
}

輸出

The minimum number of steps required to convert the first string to another by flipping the prefixes is 2

時間和空間複雜度

上述程式碼的時間複雜度為 O(N)，其中 N 是字串的長度。

由於我們不使用任何額外的空間，因此上述程式碼的空間複雜度為 O(1)。

注意

在這個問題中，我們得到兩個字串的長度相同，因此我們沒有為它編寫任何條件，但如果沒有給出，則我們必須為此新增一個條件，並檢查如果長度不同，則返回是不可能的。

結論

在本教程中，我們實現了一個程式，透過翻轉字首將二進位制字串轉換為另一個字串，並使翻轉次數最少。字首是從第零個索引開始的子字串，其長度可以是 1 到給定字串長度的任何值。我們實現了一個程式，其時間複雜度為 O(N)，空間複雜度為 O(1)。