Giả sử chúng ta có một chuỗi nhị phân, một số nguyên k khác. Chúng ta phải kiểm tra xem chuỗi có chứa tất cả các hoán vị của nhị phân k bit hay không. Giả sử một chuỗi giống như “11001”, và nếu K =2, thì nó phải có tất cả các hoán vị của k số bit. (00, 01, 10, 11), chuỗi đã cho có tất cả các hoán vị. Vì vậy, đây là chuỗi hợp lệ.
bằng cách lấy chuỗi nhị phân và giá trị của k, chúng ta phải kiểm tra xem các chuỗi nhị phân có khớp nhau hay không. Dãy nhị phân có kích thước là k. Vì vậy sẽ có 2k số hoán vị nhị phân khác nhau. Chúng tôi sẽ lưu trữ tất cả các hoán vị của giá trị nhị phân độ dài k dưới dạng chuỗi trong một danh sách, sau đó so sánh tất cả các phần tử có trong danh sách dưới dạng tập con của chuỗi đã cho. Nếu chúng ta nhận được true cho tất cả các chuỗi có trong danh sách, thì chuỗi đó hợp lệ, ngược lại thì không.
Ví dụ
#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";
}
} Đầu ra
Has All Permutations