C++ 将11替换为0后可能的不同二进制串的个数

二进制串是只包含两种不同字符零和一的字符串。我们可以将给定字符串中的子串’11’替换为另一个字符串’0’，并且我们要找出能从中得到的不同可能字符串的数量。我们将使用动态规划来解决这个问题，因为其他方法可能需要指数级的时间复杂度。

示例

输入

string str = 11010

输出

2

解释

我们可以将前两个数字替换为零，得到另一个字符串0010，第二个字符串是给定的字符串。

暴力解法

在这里，暴力解法不会表现得更好，因为我们得到的时间复杂度是指数级的。我们需要逐个将每个子字符串的’11’更改为’0’，然后找到准确的计数。

为了改善暴力方法的时间复杂度，我们将使用记忆化技术，这实际上是一种动态规划的方法，通过存储已经计算过的每种情况。

动态规划法

在这个方法中，我们将遍历字符串并存储可以形成的每个索引的情况数，然后通过对该数组进行遍历来获得最终结果。

示例

#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)，因为我们使用了一个额外的数组来存储结果。

内存高效的动态规划法

在之前的代码中，我们存储了每个索引值，但我们只需存储最后三个索引值即可得到答案。

因此，在此方法中，我们将使空间复杂度为常数。

示例

#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”。我们解释了暴力方法，效率较低，随后我们实现了动态规划方法，有两种方式，时间复杂度为线性，并且空间复杂度为线性和常数。