Medium

题目描述

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

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串为 "00"、"01"、"10" 和 "11"。它们分别在下标 0、1、3、2 处出现。

示例 2：

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

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 不存在于字符串中。

提示：

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

解题思路

解题思路

这道题需要检查字符串 s 是否包含所有长度为 k 的二进制子串。

核心观察

  1. 长度为 k 的二进制串总共有 2^k 个（从 000...0 到 111...1）
  2. 我们需要遍历字符串 s 中所有长度为 k 的子串，收集不重复的子串
  3. 如果收集到的不重复子串数量等于 2^k，则说明包含了所有可能的二进制串

优化策略

  • 提前终止：如果字符串长度小于需要的最小长度，直接返回 false
  • 字符串长度至少需要 k + 2^k - 1 才可能包含所有二进制串
  • 使用哈希集合存储已见过的子串，避免重复计算

算法步骤

  1. 检查字符串长度是否满足最小要求
  2. 使用滑动窗口遍历所有长度为 k 的子串
  3. 将每个子串加入哈希集合
  4. 检查哈希集合大小是否等于 2^k

推荐解法：哈希集合 + 滑动窗口，时间复杂度最优。

代码实现

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int need = 1 << k; // 2^k
        if (s.length() < k + need - 1) return false;
        
        unordered_set<string> seen;
        for (int i = 0; i <= (int)s.length() - k; i++) {
            seen.insert(s.substr(i, k));
            if (seen.size() == need) return true;
        }
        return false;
    }
};

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        need = 1 << k  # 2^k
        if len(s) < k + need - 1:
            return False
        
        seen = set()
        for i in range(len(s) - k + 1):
            seen.add(s[i:i+k])
            if len(seen) == need:
                return True
        return False

public class Solution {
    public bool HasAllCodes(string s, int k) {
        int need = 1 << k; // 2^k
        if (s.Length < k + need - 1) return false;
        
        HashSet<string> seen = new HashSet<string>();
        for (int i = 0; i <= s.Length - k; i++) {
            seen.Add(s.Substring(i, k));
            if (seen.Count == need) return true;
        }
        return false;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasAllCodes = function(s, k) {
    if (s.length < k) return false;
    
    const needed = 1 << k;
    if (s.length < needed + k - 1) return false;
    
    const seen = new Set();
    
    for (let i = 0; i <= s.length - k; i++) {
        seen.add(s.substring(i, i + k));
        if (seen.size === needed) return true;
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
哈希集合 + 滑动窗口O(n * k)O(k * 2^k)

其中 n 为字符串长度。时间复杂度中的 k 来自于字符串截取操作，空间复杂度中最多存储 2^k 个长度为 k 的字符串。