C++ 找出给定大小的二进制字符串数组中不存在的任意排列

在这个问题中，我们需要找出数组中长度为N的所有缺失的二进制字符串。我们可以通过找出长度为N的二进制字符串的所有排列，并检查哪些排列在数组中不存在来解决这个问题。在这里，我们将看到使用迭代和递归的方法来解决这个问题。

问题陈述 - 给定一个包含长度不同的二进制字符串的数组arr[]，我们需要找出数组中长度为N的所有缺失的二进制字符串。

示例

输入 - arr = {“111”, “001”, “100”, “110”}, N = 3

输出 - [000, 010, 011, 101]

说明 - 长度为3的二进制字符串有8个，即2的3次方等于8。所以，它打印出长度为3的缺失的4个二进制字符串。

输入 - str = {’00’, ’10’, ’11’}, N = 2

输出 - [’01’]

说明 - 因为数组中缺少’01’，所以它以输出的形式打印出来。

方法1

这里，我们将使用迭代的方法来找到长度为N的所有可能的二进制字符串。然后，我们将检查该字符串是否存在于数组中。如果不存在，则打印该字符串。

步骤

定义一个集合并使用insert()方法将数组中的所有字符串添加到集合中。
将total变量初始化为2的N次方，即长度为N的字符串的总数。
定义’cnt’变量并将其初始化为零，用于存储缺失的组合的总数。
使用循环来进行’total’次迭代，以找到长度为N的所有二进制字符串。
在循环中，将’num’字符串变量初始化为空字符串。
使用嵌套循环进行N次迭代，并从后向前创建长度为N的字符串。
使用find()方法来检查集合是否包含当前字符串。如果是，则将’cnt’的值增加1。
如果该字符串不在集合中，则将其打印出来以在输出中显示。
如果’cnt’的值等于’total’，这意味着数组中存在长度为N的所有字符串，并打印“-1”。

示例

#include <bits/stdc++.h>
using namespace std;
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {
   unordered_set<string> set;
   // insert all the strings in the set
   for (string temp : arr) {
      set.insert(temp);
   }
   // get total combinations for the string of length N
   int total = (int)pow(2, N);
   // To store combinations that are present in an array
   int cnt = 0;
   // find all the combinations
   for (int p = 0; p < total; p++) {
      // Initialize empty binary string
      string bin = "";
      for (int q = N - 1; q >= 0; q--) {
          // If the qth bit is set, append '1'; append '0'.
          if (p & (1 << q)) {
              bin += '1';
          } else {
              bin += '0';
          }
      }
      // If the combination is present in an array, increment cnt
      if (set.find(bin) != set.end()) {
          cnt++;
          continue;
      } else {
          cout << bin << ", ";
      }
   }
   // If all combinations are present in an array, print -1
   if (cnt == total) {
      cout << "-1";
   }
}
int main() {
   int N = 3;
   vector<string> arr = {"111", "001", "100", "110"};
   printMissingCombinations(arr, N);
   return 0;
}

输出

000, 010, 011, 101,

时间复杂度 – O(N*2N)，其中O(N)用于检查字符串是否存在于数组中，O(2N)用于找出所有可能的排列。

空间复杂度 – O(N)，因为我们使用集合来存储字符串。

方法2

在这种方法中，我们演示了使用递归方法来找到长度为N的所有可能的二进制字符串。

步骤

定义集合并将所有数组值插入集合中。
调用generateCombinations()函数生成所有二进制字符串的组合。
在generateCombinations()函数中定义基本情况。如果索引等于N，则将当前组合推送到列表中。
- 在将“0”或“1”附加到当前组合之后，递归调用generateCombinations()函数。
在获取所有组合之后，检查哪些组合存在于数组中，哪些组合不存在。同时打印缺失的组合以显示在输出中。

示例

#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible combinations of binary strings
void generateCombinations(int index, int N, string currentCombination, vector<string> &combinations) {
   // Base case: if we have reached the desired length N, add the combination to the vector
   if (index == N) {
      combinations.push_back(currentCombination);
      return;
   }
   // Recursively generate combinations by trying both 0 and 1 at the current index
   generateCombinations(index + 1, N, currentCombination + "0", combinations);
   generateCombinations(index + 1, N, currentCombination + "1", combinations);
}
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {    
   unordered_set<string> set;
   // insert all the strings in the set
   for (string str : arr) {
      set.insert(str);
   }
   // generating all combinations of binary strings of length N
   vector<string> combinations;
   generateCombinations(0, N, "", combinations);
   // Traverse all the combinations and check if it is present in the set or not
   for (string str : combinations) {
      // If the combination is not present in the set, print it
      if (set.find(str) == set.end()) {
          cout << str << endl;
      }
   }

   return;
}
int main(){
   int N = 3;
   vector<string> arr = {"111", "001", "100", "110"};
   printMissingCombinations(arr, N);
   return 0;
}