README.md

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

English Version

题目描述

给你一个二进制字符串 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 <= s.length <= 5 * 10^5
• s 中只含 0 和 1 。
• 1 <= k <= 20

解法

遍历字符串 s，用一个 set 存储所有长度为 k 的不同子串。只需要判断子串数能否达到 2^k 即可。

Python3

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        counter = 1 << k
        exists = set()
        for i in range(k, len(s) + 1):
            if s[i - k: i] not in exists:
                exists.add(s[i - k: i])
                counter -= 1
            if counter == 0:
                return True
        return False

Java

class Solution {
    public boolean hasAllCodes(String s, int k) {
        int counter = 1 << k;
        Set<String> exists = new HashSet<>();
        for (int i = k; i <= s.length(); ++i) {
            String t = s.substring(i - k, i);
            if (!exists.contains(t)) {
                exists.add(t);
                --counter;
            }
            if (counter == 0) {
                return true;
            }
        }
        return false;
    }
}

...