1461. Check If a String Contains All Binary Codes of Size K 检查一个字符串是否包含所有长度为 K 的二进制子串

题目地址: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 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发