计算二进制字符串中替换“？”字符可能产生的排列数

---

在这个问题中，我们给定一个包含 0、1 和“？”字符的字符串。我们需要通过用 0 和 1 替换“？”来找到字符串的排列。解决问题的逻辑是，我们可以用 0 或 1 替换每个“？”。因此，通过替换一个“？”，我们可以生成两个不同的排列，并且通过用 2 种可能性替换 N 个“？”，我们可以生成 2^N 个排列。

在本教程中，我们将学习两种不同的方法来解决给定的问题。

问题陈述 – 我们给定一个包含“0”、“1”和“？”字符的字符串 str。我们需要用 0 或 1 替换“？”并找到给定字符串的所有排列。

示例

输入 – str = "0101001??01"

输出 – 4

解释 – 4 个不同的组合是 01010010101、01010011001、01010010001 和 01010011101

输入 – str = ’01?0’

输出 – 2

解释 – 2 个不同的组合是 0100 和 0110。

输入 – str = ‘01010’

输出 – 1

解释 – 给定的字符串本身就是一个排列。

方法 1

在这种方法中，我们将通过遍历字符串来计算给定字符串中“？”的总数。之后，我们将使用左移运算符获取 2^N，其中 N 是字符串中“？”的总数。

算法

• 定义变量“cnt”并初始化为 0，以存储给定字符串中“？”的数量

• 使用循环遍历字符串。如果当前字符是“？”，则将“cnt”变量的值增加 1。

• 使用左移运算符获取 2cnt 并将其存储到“perm”变量中。

• 返回“perm”变量的值

示例

#include <iostream>
using namespace std;

// function to count the number of permutations of the given string by replacing '?' with '0' or '1'
int totalPermutations(string s){
   // variable to store the count of '?' in the string
   int cnt = 0;
   // loop to count the number of '?' in the string
   for (int i = 0; i < s.length(); i++){
      if (s[i] == '?'){
         cnt++;
      }
   }
   // total number of permutations of the string by replacing'?' with '0' or '1' is 2^cnt
   int perm = 0;
   //   calculating 2^cnt with left shift operator
   perm = 1 << cnt;
   return perm;
}
int main(){
   string str = "0101001??01";
   cout << "The total number of permutations of the string we can get by replacing ? with 0 or 1 is " << totalPermutations(str);
   return 0;
}

输出

The total number of permutations of the string we can get by replacing ? with 0 or 1 is 4

时间复杂度 – O(N)，因为我们遍历了字符串。

空间复杂度 – O(1)，因为我们没有使用动态空间。

方法 2

在这种方法中，我们将使用 count() 方法来计算给定字符串中“？”字符的总数。之后，我们使用 pow() 方法计算 2^N。

算法

• 定义变量“cnt”并将其初始化为零。

• 使用 count() 方法计算给定字符串中“？”出现的总数。我们需要将字符串的起始点作为第一个参数，结束点作为第二个参数，以及“？”作为第三个参数传递。

• 使用 pow() 方法获取 2cnt。

• 返回“perm”值。

示例

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

// function to count the number of permutations of the given string by replacing '?' with '0' or '1'
int totalPermutations(string s){
   // variable to store the count of '?' in the string
   int cnt = 0;
   //    using the count() function to count the number of '?' in the string
   cnt = count(s.begin(), s.end(), '?');
   int perm = 0;
   //   calculating 2^cnt using the pow() function
   perm = pow(2, cnt);
   return perm;
}
int main(){
   string str = "0101001??01";
   cout << "The total number of permutations of the string we can get by replacing ? with 0 or 1 is " << totalPermutations(str);
   return 0;
}

输出

The total number of permutations of the string we can get by replacing ? with 0 or 1 is 4

时间复杂度 – O(N)，因为 count() 方法迭代长度为 N 的字符串。

空间复杂度 – O(1)

我们学习了两种不同的方法来计算通过用 0 或 1 替换“？”字符可以获得的排列总数。程序员可以使用左移运算符的 pow() 方法来计算 2N。