ตรวจสอบว่าสตริงมีรหัสไบนารีขนาด K ครบทุกแบบใน C++

สมมติว่าเรามีสตริงไบนารี s และจำนวนเต็ม k เราต้องตรวจสอบว่ารหัสไบนารีความยาว k ทุกแบบเป็น substring ของ s หรือไม่

ตัวอย่าง: S = "00110110", k = 2 ผลลัพธ์ = true รหัสความยาว 2 คือ "00", "01", "10", "11" อยู่ที่ index 0,1,3,2 ตามลำดับ

วิธีแก้ปัญหา (Sliding Window + Hash Set)

ใช้ sliding window ขนาด k เดินผ่าน s
เก็บ substring ที่เจอใน hash set
ถ้าจำนวนใน set เท่ากับ 2^k คืน true ทันที
จบลูปไม่ครบคืน false

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

typedef long long int lli; 

class Solution { 
public: 
    lli fastPow(lli b, lli p){ 
        lli ret = 1; 
        while (p) { 
            if (p & 1) ret *= b; 
            b *= b; 
            p >>= 1; 
        } 
        return ret; 
    } 
    
    bool hasAllCodes(string s, int k) { 
        unordered_set<string> v; 
        string temp = ""; 
        lli req = fastPow(2, k); 
        for (lli i = 0; i < s.size(); i++) { 
            temp += s[i]; 
            if (i >= k) temp.erase(0, 1); 
            if (i >= k - 1) v.insert(temp); 
            if ((lli)v.size() == req) return true; 
        } 
        return false; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.hasAllCodes("00110110",2)); 
}

ข้อมูลนำเข้า

"00110110",2