[LeetCode-Python版] 定长滑动窗口3——1461. 检查一个字符串是否包含所有长度为 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 * 105
• s[i] 不是’0’ 就是 ‘1’
• 1 <= k <= 20

题目链接

我的思路

统计不同的子串，最后看子串数目是不是$2^k$

思路不足：
没有考虑时间复杂度和空间复杂度，导致时间超出限制

我的代码

class Solution:def hasAllCodes(self, s: str, k: int) -> bool:if len(s) < 2**k : return Falsestring = ""pattern = []for i,c in enumerate(s):string += cif i < k-1 :continueif string not in pattern:pattern.append(string)string = string[1:]return len(pattern) == 2**k

题解思路

题解思路和我的一样，但是代码上进行了优化

参考代码

class Solution:def hasAllCodes(self, s: str, k: int) -> bool:if len(s) < 2**k : return Falsepattern = set()for r in range(len(s)):if r < k-1 : continuepattern.add(s[r-k+1:r+1])return len(pattern) >= 2**k    

Q&A

1. 为什么我的代码会超出限制，而题解代码不会？

• 字符串操作效率低：
  • 我的代码用string = string[1:] ，这个操作在每次循环中都会创建一个新的字符串，这是低效的。可以使用索引来避免不必要的字符串复制。
  • 题解代码用pattern.add(s[r-k+1:r+1]) 字符串切片来获取长度为 k 的子串，而不是像之前那样通过累加字符来构建字符串。这种方法更加高效，因为它避免了在循环中重复构建字符串。
• 集合的使用:
  • 我的代码中if string not in pattern的时间复杂度是 O(n)，其中 n 是 pattern 列表的长度。随着 pattern 列表的增长，这个检查会变得越来越慢。
  • 题解代码中用集合set()来存储子串，可以确保每个子串只被添加一次，并且检查一个元素是否存在于集合中的时间复杂度是 O(1)，这比列表的 O(n) 要快得多。