数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学检查二进制字符串在 C++ 中是否包含所有长度为 k 的排列
假设我们有一个二进制字符串，另外一个整数 k。我们必须检查字符串是否包含 k 位二进制的所有排列。假设一个字符串类似于 “11001”，如果 K = 2，则它必须具有 k 位数字的所有排列。(00, 01, 10, 11)，给定的字符串具有所有排列。因此，这是有效的字符串。
通过获取二进制字符串和 k 的值，我们必须检查二进制序列是否匹配。二进制序列的大小为 k。因此，将有 2k 个不同的二进制排列。我们将在列表中将所有 k 长度二进制值的排列存储为字符串，然后比较列表中存在的所有元素作为给定字符串的子集。如果我们对列表中存在的所有字符串都得到 True，则字符串有效，否则无效。
示例
#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 << "Has All Permutations";
} else {
cout << "Not All Permutations are found";
}
}输出
Has All Permutations
更新于:22-Oct-2019
103 次浏览
广告