[LeetCode] 1461. Check If a String Contains All Binary Codes of Size K

• 難度分: 1504
• 比較簡單的解法，使用 unordered_set

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> set;
        for (int i = 0; i + k <= s.size(); i++) {
            set.insert(s.substr(i, k));
        }
        return set.size() == pow(2, k);
    }
};

• 使用 sliding window，並運用移位運算子

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        if (s.size() < k) return false;
        int n = pow(2, k);
        vector<bool> used(n, false);
        int curr = 0;
        for (int i = 0; i < k; i++) {
            curr <<= 1;
            curr += (s[i] - '0');
        }
        used[curr] = true;
        for (int i = k; i < s.size(); i++) {
            curr <<= 1;
            curr += (s[i] - '0');
            curr %= n;
            used[curr] = true;
        }
        return all_of(used.begin(), used.end(), [](int x) { return x; });
    }
};