代码超出时间限制：检查字符串是否包含大小为 K 的所有二进制代码

Question

我正在尝试解决LeetCode问题1461。检查字符串是否包含大小为 K 的所有二进制代码:

给定一个二进制字符串

s

和一个整数

k

，如果每个长度为 true 的二进制代码都是

k

的子串，则返回 s

。否则，返回

false

。

思考过程

列出长度为

k

 的所有可能的二进制字符串（将其命名为 

binary

）。然后使用滑动窗口迭代字符串，并针对每个窗口检查该窗口是否存在于名为 

binary

 的列表中。如果列表为空，则意味着它满足所有可能的字符串。如果它不为空，则意味着它不包含所有可能的二进制代码，并将返回 false。

代码

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)

问题

在上面的代码片段中包含的最后一个测试中，我收到了超出时间限制的错误。我应该改进什么？

Answer 1

列表

pop(0)

 和 

remove

 方法的时间复杂度很差。

使用集合来工作会更有效率，让它成为一组

int

而不是字符串。如果您从一个

空集开始，然后向其添加扫描输入字符串时找到的值，速度也会更快。

跟踪您在主循环中检查的 k 大小“窗口”的

value 是多少。当窗口向前滑动一个位置时，您可以轻松地通过以下方式更新值：

乘以 2 为新数字腾出空间
向其中添加新数字（0 或 1）
通过使用模运算（或应用位掩码）删除“旧”数字

然后将这些值

添加到set

。您可以从该集合的大小看出是否收集了所有二进制数。

以下是剧透解决方案：

    def hasAllCodes(self, s, k):
         binary = set()  # Start with empty set.
         n = len(s)
         value = int("0" + s[:k-1], 2)  # Avoid error when k=1 and prepad a zero
         mod = 1 << k   # This is 2**k, but as an integer operation
         for digit in s[k-1:]:
             value = (value * 2 + int(digit)) % mod  # Slide the window
             binary.add(value)
             if len(binary) == mod:  # We found all binary numbers?
                 return True
         return False