检查二进制字符串是否包含C ++中长度为k的所有排列
假设我们有一个二进制字符串，另一个整数k。我们必须检查字符串是否包含k位二进制的所有排列。假设一个字符串像“11001”，并且如果K=2，则它必须具有k位数字的所有排列。(00,01,10,11)，给定的字符串具有所有排列。因此，这是有效的字符串。
通过获取二进制字符串和k的值，我们必须检查二进制序列是否匹配。二进制序列的大小为k。因此，将有2k个不同的二进制排列。我们将把长度为k的二进制值的所有排列作为字符串存储在列表中，然后将列表中存在的所有元素作为给定字符串的子集进行比较。如果我们对列表中存在的所有字符串都为真，则该字符串有效，否则无效。
示例
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<string> binaryPermutations(int k){
vector<string> list;
int n = 0;
string bin_str = "";
for(int i = 0; i<k; i++){
bin_str += "0";
}
int limit = pow(2, k);
list.push_back(bin_str);
for(int i=1; i<limit; i++){
int j = 0;
while(j <= k){
if(bin_str[k-1-j] == '0'){
bin_str[k - 1 - j] = '1';
break;
} else {
bin_str[k - 1 - j] = '0';
j++;
}
}
list.push_back(bin_str);
}
return list;
}
bool hasAllPermutation(string str, int k){
vector<string> list = binaryPermutations(k);
for(int i = 0; i<list.size(); i++){
string substr = list[i];
std::size_t found = str.find(substr);
if(found == std::string::npos){
return false;
}
}
return true;
}
int main() {
int k = 2;
string str = "11001";
if(hasAllPermutation(str, k)){
cout << "具有所有排列";
} else {
cout << "找不到所有排列";
}
}输出结果
具有所有排列