LeetCode 1461题代码超时求助：检查字符串是否含所有k位二进制码

题目描述 #

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

初始思路与代码 #

我的思路是先生成所有长度为k的二进制字符串列表，再用滑动窗口遍历s，检查每个窗口是否在列表中，若存在则移除该元素，最终判断列表是否为空。

代码如下：

class Solution(object):
    def hasAllCodes(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        if k > len(s):
            return False
        binary = [""]
        for i in range(k):
            N = len(binary)
            for i in range(N):
                a = binary.pop(0)
                binary.append(a + "0")
                binary.append(a + "1")

        n=len(s)
        i=j=0
        sSoFar=""
        while j<n:
            sSoFar+=s[j]
            if j>=k-1:
                if sSoFar in binary:
                    binary.remove(sSoFar)
                sSoFar=sSoFar[1:]
                i+=1
            j+=1


        #print(binary)
        return len(binary)==0


solution = Solution()
a = solution.hasAllCodes("00110110", 2) #expected true
print(a)
a = solution.hasAllCodes("0110", 1) #expected true
print(a)
a = solution.hasAllCodes("0110", 2) #expected false
print(a)
a = solution.hasAllCodes("1011110111001001101001110001100111101111010101011100111001110010010001000111010110101110000110101001011100100010100110011101011110001000100010101101011", 20) #expected false
print(a)

遇到的问题 #

最后一个测试用例出现Time Limit Exceeded错误，请问该如何优化？

优化方案 #

问题根源 #

代码超时主要有两个核心原因：

1. 列表操作效率低下：列表的in判断和remove操作都是O(n)时间复杂度，当k=20时，列表大小为2^20=1048576，每次操作都要遍历整个列表，时间开销极大。
2. 字符串拼接冗余：手动拼接sSoFar并截断的方式会频繁生成新字符串，额外增加时间消耗。

具体优化步骤 #

1. 用集合替代列表存储目标二进制串

集合的in判断和remove操作都是O(1)复杂度，能大幅降低时间开销。生成所有长度为k的二进制串时直接存入集合即可。

2. 优化滑动窗口的字符串处理

直接通过字符串切片获取窗口子串，避免手动拼接和截断，代码更简洁高效。

3. 提前终止判断

当集合为空时，直接返回True，无需继续遍历剩余字符串，节省不必要的计算。

优化后的代码（生成目标集合版本） #

class Solution(object):
    def hasAllCodes(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        n = len(s)
        if k > n:
            return False
        # 计算所有长度为k的二进制串总数
        total = 1 << k  # 等价于2^k
        # 生成所有长度为k的二进制串并存入集合
        required = set()
        for num in range(total):
            # 将数字转为固定长度k的二进制字符串，补前导0
            binary_str = bin(num)[2:].zfill(k)
            required.add(binary_str)
        
        # 滑动窗口遍历s
        for i in range(n - k + 1):
            current = s[i:i+k]
            if current in required:
                required.remove(current)
                # 提前终止，无需继续遍历
                if not required:
                    return True
        # 遍历结束后检查集合是否为空
        return len(required) == 0

更高效的反向收集思路 #

不需要先生成所有二进制串，直接收集s中所有长度为k的子串存入集合，最后判断集合大小是否等于2^k。这种方式省去了生成所有二进制串的步骤，效率更高：

class Solution(object):
    def hasAllCodes(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        n = len(s)
        if k > n:
            return False
        total = 1 << k
        seen = set()
        for i in range(n - k + 1):
            substr = s[i:i+k]
            seen.add(substr)
            # 提前终止，一旦数量达标直接返回
            if len(seen) == total:
                return True
        return len(seen) == total

这个版本时间复杂度为O(n*k)（每个子串生成是O(k)），空间复杂度为O(min(2^k, n))，对于k=20的场景，2^20的集合大小在内存允许范围内，且遍历过程中提前终止的逻辑能有效避免超时。

内容的提问来源于stack exchange，提问作者Karina