Solutions CS101

Appearance

M1461.检查一个字符串是否包含所有长度为 K 的二进制子串 ​

bit manipulation, https://leetcode.cn/problems/check-if-a-string-contains-all-binary-codes-of-size-k/

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

提示：

  • 1 <= s.length <= 5 * 10^5
  • s[i] 不是'0' 就是 '1'
  • 1 <= k <= 20

这道题的核心任务是判断在给定的二进制字符串 s 中，是否包含了所有可能出现的长度为 k 的二进制子串。

长度为 k 的二进制子串共有 2k 种组合。为了验证是否所有组合都在 s 中出现过，最直观且高效的方法是：遍历 s 中所有的长度为 k 的子串，将其放入集合（Set）中去重，最后判断集合的大小是否等于 2k。

在此思路上，我们可以进行一次早停优化（Early Exit）：

  • 字符串 s 中长度为 k 的子串最多有 len(s) - k + 1 个。
  • 如果哪怕这 len(s) - k + 1 个子串各不相同，它的总数依然小于 2k，那么必然无法包含所有的组合，可以直接返回 False，避免后续多余的计算。

方法一：哈希集合（最推荐的 Pythonic 解法）

利用 Python 内置高度优化的切片和集合推导式，代码非常简练且执行速度极快。

python
class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        # 早停优化：如果子串的最大可能数量小于 2^k，直接返回 False
        if len(s) - k + 1 < (1 << k):
            return False
        
        # 使用集合推导式获取所有长度为 k 的子串，通过 set 去重
        # 检查最终去重后的子串种类数是否等于 2^k (即 1 << k)
        return len({s[i:i+k] for i in range(len(s) - k + 1)}) == (1 << k)

复杂度分析（方法一）

  • 时间复杂度：O(N⋅k)，其中 N 是字符串 s 的长度。我们需要提取 N−k+1 个长度为 k 的子串并存入哈希表。由于 k≤20，k 可以视作小常数。
  • 空间复杂度：O(2k⋅k)。哈希集合中最多会保存 2k 个不同的子串，每个子串长度为 k。题目限定 k≤20，而且在早停优化的保护下，最大可能被记录的字符串数量远在内存限制内。

方法二：滚动哈希 / 位运算（进阶思路）

我们也可以不利用切片生成新的字符串，而是将长度为 k 的二进制字串看做一个十进制整数。比如子串 "101" 可以用 5 表示。使用位运算能够做到 O(1) 地更新哈希值（即滑动窗口右移一位，左移抛弃最高位，末位加上新进来的字符）。

python
class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        # 同样进行早停优化
        req = 1 << k
        if len(s) - k + 1 < req:
            return False
        
        # seen 使用 bytearray 充当布尔数组，速度比 list 快，占用空间也很小
        seen = bytearray(req)
        seen = [0]*req
        
        # 初始化前 k-1 个字符组成的数值
        num = int(s[:k-1], 2) if k > 1 else 0
        mask = req - 1
        count = 0
        
        # 滑动窗口遍历
        for i in range(k - 1, len(s)):
            # 移位，按位与去最高位，加上新进来的最后一位字符
            num = ((num << 1) & mask) | (1 if s[i] == '1' else 0)
            
            # 如果是第一次见到这个数字组合
            if not seen[num]:
                seen[num] = 1
                count += 1
                # 当不同组合凑齐 2^k 种，说明包含了所有情况
                if count == req:
                    return True
                    
        return False

复杂度分析（方法二）

  • 时间复杂度：O(N)，位运算滚动更新只需要 O(1) 时间，整体只需线性扫描一遍。
  • 空间复杂度：O(2k)，布尔数组固定开辟 2k 个位置的空间。相比集合存字符串极大地节省了内存占用。