题目地址：https://leetcode-cn.com/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 = "00110", k = 2
输出：true
示例3：
输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
示例4：
输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
示例5：
输入：s = "0000000001011100", k = 4
输出：false
提示：
1、 1<=s.length<=5*10^5；
2、 s中只含0和1；
3、 1<=k<=20；
题目大意
检查一个字符串是否包含所有长度为 K 的二进制子串。
解题方法
统计长度为 K 的子串个数
第一想法：把长度为 K 的所有二进制全部找出来，然后判断是否都在 s 中出现了。该方法的复杂度是 O(2^K * len(s))，大概是 10 ^ 11的级别，一定会超时。
所以反过来想， s 中长度为 K 的所有不同的子串数目是否有 2 ^ K 个呢。如果是的话，说明 s 中包含所有长度为 K 的二进制子串。
代码是set + 子字符串 实现的。
时间复杂度是 O(N*k)，N 是 s 的长度，乘以 k 是截取获得子字符串的操作时间复杂度。 空间复杂度是 O(2 ^ k)。
Python 代码如下：
class Solution(object):
def hasAllCodes(self, s, k):
"""
:type s: str
:type k: int
:rtype: bool
"""
contains = set()
N = len(s)
for i in range(N - k + 1):
contains.add(s[i:i + k])
return len(contains) == (2 ** k)
1 2 3 4 5 6 7 8 9 10 11 12
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发