Kiểm tra chuỗi nhị phân chứa tất cả hoán vị độ dài k C++

Cho chuỗi nhị phân và số k. Kiểm tra chuỗi có chứa tất cả 2ᵏ hoán vị của chuỗi nhị phân độ dài k không.

Ví dụ: str="11001", k=2. Các hoán vị 2-bit: 00, 01, 10, 11. Chuỗi chứa tất cả → YES.

Giải thuật

1. Sinh tất cả 2ᵏ chuỗi nhị phân độ dài k
2. Với mỗi chuỗi, kiểm tra có phải substring của str không (str.find)
3. Nếu thiếu bất kỳ chuỗi nào → false

Ví dụ minh họa

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
using namespace std;

vector<string> binaryPermutations(int k) {
    vector<string> list;
    string bin_str(k, '0');
    list.push_back(bin_str);
    
    int limit = pow(2, k);
    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 (string substr : list)
        if (str.find(substr) == string::npos)
            return false;
    return true;
}

int main() {
    string str = "11001";
    int k = 2;
    cout << (hasAllPermutation(str, k) ? "Chua tat ca hoan vi" : "Thieu hoan vi");
}

Kết quả

Chua tat ca hoan vi