[LeetCode] 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 * 10⁵
s[i] 不是'0' 就是 '1'
1 <= k <= 20

思路:

所有长度为k的二进制字符串一共 2^k 种，那么只需要用长度为k的滑动窗口看看二进制字符串 s 有多少种长度为 k 的子字符串就知道是不是包含所有长度为 k 的二进制子串了。1 <= k <= 20，所以用一个哈希表 unordered_set<int> seen;就能存下所有长度为 k 的子字符串，其最大尺寸不过 2²⁰。

实现滑动窗口就是每次去掉最窗口左边的位，在窗口右边加入新位。因此用 (window << 1) 将窗口左移一位，再 & mask 来去掉最高位，最后用 (s[i] - '0') 加上窗口右边的最低位，这时窗口内就是新的子串值了。

AC代码:

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int n = s.length();
        if (n < k) return false;
        
        int totalNeeded = 1 << k;
        if (n - k + 1 < totalNeeded) return false;
        
        unordered_set<int> seen;
        int mask = totalNeeded - 1;

        int window = 0;
        for (int i = 0; i < k; i++) {
            window = (window << 1) | (s[i] - '0');
        }
        seen.insert(window);
        
        for (int i = k; i < n; i++) {
            window = ((window << 1) & mask) | (s[i] - '0');
            
            seen.insert(window);
            if (seen.size() == totalNeeded) return true;
        }
        
        return seen.size() == totalNeeded;
    }
};Code language: C++ (cpp)

网上的一种用 bitset 的更快做法：

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int req = 1 << k;
        bitset<1048576> seen;
        int mask = req - 1;
        int hash = 0;

        for (int i = 0; i < s.length(); ++i) {
            hash = ((hash << 1) & mask) | (s[i] & 1);

            if (i >= k - 1 && !seen[hash]) {
                seen[hash] = 1;
                req--;
                if (req == 0) return true;
            }
        }

        return false;
    }
};Code language: PHP (php)