题目描述

给定一个二进制字符串 s 和一个整数 k。

如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 True，否则请返回 False。

样例

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。
它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

输入：s = "00110", k = 2
输出：true

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

输入：s = "0000000001011100", k = 4
输出：false

限制

• 1 <= s.length <= 5 * 10^5
• s 中只含 0 和 1。
• 1 <= k <= 20

算法

(暴力枚举) $O(n + 2^k)$

1. 遍历 s 中所有长度为 k 的子串。
2. 遍历时，求子串所代表的数字时，每次仅需要常数次的位运算。
3. 最后，判定是否所有数字都出现过。

时间复杂度

• 仅需要遍历字符串一次，遍历长度为 $k$ 的所有二进制数，故时间复杂度为 $O(n + 2^k)$。

空间复杂度

• 需要额外 $O(2^k)$ 的空间记录是否每个数字都出现过。

C++ 代码

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        if (k > s.size())
            return false;

        vector<bool> v(1 << k, false);
        int t = 0;

        for (int i = 0; i < k - 1; i++)
            t = (t << 1) | (s[i] - '0');

        for (int i = k - 1; i < s.size(); i++) {
            t = (t << 1) | (s[i] - '0');
            v[t] = true;
            t &= (1 << k - 1) - 1;
        }

        for (int i = 0; i < (1 << k); i++)
            if (!v[i])
                return false;

        return true;
    }
};