替換 11 為 0 後可能的不同二進位制字串的數量

---

二進位制字串是指僅包含兩種不同字元（零和一）的字串。我們可以將給定字串的子字串“11”替換為另一個字串“0”，並且我們必須找到可以從中獲得的不同字串的數量。我們將使用動態規劃來獲得解決方案，因為其他方法可能需要指數時間複雜度。

示例

輸入

string str = 11010

輸出

2

解釋

我們可以將前兩個數字替換為零，並得到另一個字串 0010，第二個字串是給定的字串。

暴力法

暴力法在這裡不會表現得更好，因為我們得到的時指數時間複雜度。我們需要一個接一個地將每個“11”子字串更改為“0”，然後我們將找到確切的計數。

為了提高暴力法的時效性，我們將使用備忘錄技術，這實際上就是動態規劃方法，在其中我們將儲存每個已經計算出的情況。

方法 1：動態規劃

在這種方法中，我們將遍歷字串並存儲當前索引可以形成的情況數，然後透過遍歷該陣列獲得最終結果。

示例

#include <bits/stdc++.h>
using namespace std; 

// function to get the final result 
int getCount(string str){
   int len = str.length(); // getting lenght of the string 
   vector<int>dp(len,0); // vector to store result  
   // pre-defining edge cases
   if(str[0] == '1'){
      dp[0] = 1;
   }
   if(str.substr(0,2) == "11") {
      dp[1] = 2;
   } else if (str[1] == '1') {
      dp[1] = 1;
   }
   // traversing over the string & storing the value of each step
   for (int i = 2; i < len; i++){
      if(str[i] == '1'){
         // checking for the previous index if it is also one 
         if(str[i-1] == '1'){
            // checking if the previous 2 indexes are '1' then the current spot will have two cases
            if(str[i - 2] == '1'){
               dp[i] = dp[i-1] + dp[i-2];
            } else {
               dp[i] = 2;
            }
         } else {
            // if current support is zero then there will will only one case 
            dp[i] = 1;
         }
      }
   }
   int res = 1; 
   // getting the result by multiplying the stored data with the result 
   for(int i = 1; i < len; ++i){
      if(dp[i] < dp[i-1]){
         res = res * dp[i-1];
      }
   }
    
   // storing the last bit
   if(dp[len-1] != 0){
      res = res * dp[len - 1];
   }

   return res; // returning the final result 
}

int main(){
   string str = "11011"; // given string
   // calling the given function 
   cout<<"The count of possible distinct Binary strings after replacing 11 with 0 is: " << getCount(str)<<endl;
   return 0;
}

輸出

The count of possible distinct Binary strings after replacing 11 with 0 is: 4

時間和空間複雜度

上述程式碼的時間複雜度為 O(N)，其中 N 是給定字串的大小。我們得到線性時間複雜度，因為我們只遍歷陣列一次。

上述程式碼的空間複雜度為 O(N)，因為我們使用了一個額外的陣列來儲存結果。

方法 2：記憶體高效的動態規劃

在前面的程式碼中，我們儲存了每個索引值，但是我們可以透過只儲存最後三個來獲得答案。

因此，在這種方法中，我們將使空間複雜度為常數。

示例

#include <bits/stdc++.h>
using namespace std; 

// function to get the final result 
int getCount(string str){
   int len = str.length(); // getting lenght of the string     
   int first = 0, second = 0, third = 0; 
   // pre-defining edge cases
   if(str[0] == '1'){
      first = 1;
   }
   if(str.substr(0,2) == "11") {
      second = 2;
   } else if (str[1] == '1') {
      second = 1;
   }
   // traversing over the string & storing the value of each step
   for (int i = 2; i < len; i++){
      if(str[i] == '1'){
         // checking for the previous index if it is also one 
         if(str[i-1] == '1'){
            // checking if the previous 2 indexes are '1' then the current spot will have two cases
            if(str[i - 2] == '1'){
               int cur = third;
               third = first + second;
               first = second;
               second = cur;
            } else {
               third = second;
               second = 2;
               first = second;
            }
         } else {
            // if current support is zero then there will will only one case 
            third = second;
            second = 1; 
            first = second;
         }
      } else {
         third = second;
         second = 0;
         first = second;
      }
   } 
   int res = 1; 
   // getting the result by multiplying the stored data with the result 
   if(second > third){
      res = res * second;
   } else {
      res = res * third;
   }    
   // storing the last bit
   if(first != 0){
      res = res * first;
   }
   return res; // returning the final result 
} 
int main(){
   string str = "11011"; // given string 
   // calling the given function 
   cout<<"The count of possible distinct Binary strings after replacing 11 with 0 is: " << getCount(str)<<endl;
   return 0;
}

輸出

The count of possible distinct Binary strings after replacing 11 with 0 is: 4

結論

在本教程中，我們實現了一個程式來查詢如果我們可以將任何“11”替換為“0”，則可以從給定的二進位制字串中獲得的不同字串數量。我們解釋了效率低下的暴力法，然後以兩種方式實現了動態規劃方法，具有線性時間複雜度以及線性常數空間複雜度。