MediumRating 1504

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

hash-tablestringbit-manipulationrolling-hashhash-function

在 LeetCode 上作答 ↗

解題說明

Check If a String Contains All Binary Codes of Size K

題目描述：給定一個二進位字串 s 和整數 k，判斷 s 是否包含所有長度為 k 的二進位碼作為子字串。長度為 k 的二進位碼共有 2^k 個（從 00...0 到 11...1）。

解題思路：使用滑動窗口 + HashSet。遍歷字串 s 的所有長度為 k 的子字串，將它們加入 HashSet 中。最後檢查 HashSet 的大小是否等於 2^k。

優化：可以用滾動雜湊（rolling hash）或位運算來避免每次都建立新字串。用一個整數表示當前窗口的二進位值，每次滑動時左移一位、加入新位元、遮罩掉超出 k 位的部分。用 boolean 陣列代替 HashSet 更快。

C++ 解法

複雜度分析

時間複雜度：O(n) — 單次遍歷字串，每步位運算 O(1)。最後檢查 seen 陣列 O(2^k)。

空間複雜度：O(2^k) — boolean 陣列的大小。

虛擬碼

1. Let need = 2^k, mask = need - 1
2. If s.length - k + 1 < need, return false (early exit)
3. Initialize seen array of size need (all false)
4. hash = 0
5. For i from 0 to s.length - 1:
   a. hash = ((hash << 1) | (s[i] - '0')) & mask
   b. If i >= k - 1: set seen[hash] = true
6. Return true if all entries in seen are true, else false

其他解法

HashSet + 子字串：直接用 unordered_set<string> 收集所有長度 k 的子字串。時間 O(nk)（每次子字串建立 O(k)），空間 O(k * 2^k)。簡單但效率較差。

HashSet + 整數：用 unordered_set<int> 存整數雜湊值，避免字串操作。時間 O(n)，空間 O(2^k)。與 boolean 陣列法類似，但 HashSet 有額外開銷。

延伸思考

若 k 很大（超過 32），整數無法表示，如何處理？（提示：用 string 或 bitset）
若不需要包含「所有」二進位碼，而是至少包含其中 m 個，如何修改？
此問題與 De Bruijn 序列有什麼關聯？

Check If a String Contains All Binary Codes of Size K — CaffeCode