替换 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”，则可以从给定的二进制字符串中获得的不同字符串数量。我们解释了效率低下的暴力法，然后以两种方式实现了动态规划方法，具有线性时间复杂度以及线性常数空间复杂度。