题目描述

给你一个二进制字符串 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

算法1

(暴力枚举) $O(n · k)$

• 遍历字符串s，记录截取长度为k的所有子串，统计截取的次数
• 若总截取次数为 $2^k$ 次则返回 true

时间复杂度

• 遍历一次字符串的时间复杂度是 $O(n)$;
• 每次 substr 的时间复杂度是 $O(k)$;
• set 的insert操作的时间复杂度是 $O(1)$;
• 故总的时间复杂度是 $O(n · k)$

C++ 代码

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        typedef long long LL;
        unordered_set<string> map;
        LL cnt = 0;        

        int n = s.size();
        for (int  i = 0; i <= n - k; i ++)
        {
            string str = s.substr(i, k);

            if (map.count(str)) 
                continue;

            map.insert(str);
            cnt ++;
        }

        if (cnt < (1 << k))  return false;

        return true;
    }
};

算法2

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

> 准备了一个小剧本：
* 可以想象成一条传送带：将 abcde 按照 edcba 的顺序放到传送带上；
* 在传送带的基础上加个扫描器，这个扫描器可以扫描 k 长度的产品，记录扫描过的产品；
* 最后，由于我们已知需要哪些产品，只要检查扫描过的产品里是否存在即可，不存在其中一个就返回 false

• 我们目标是找到所有 $2^k$ 个二进制子串，从左往右截取和从右往左截取的效果是一样的，但是截取的具体字符串不一样，但是这不影响最终要找齐 $2^k$ 个。
• 解释上面描述的传送带: 读取每一位二进制时，先整体左移再加上当前这位；
• 解释上面描述的扫描器：读取完后，对已读取的二进制数跟 $2^k - 1$ 进行&操作，这样会将高于k位的所有位清空为0；因为高于k位的在之前读取的时候就已经记录过了，而且清空之后得到的结果必定是落在[0, 2^k - 1]范围，说明我们找到了一个产品，可以使用map标记它已找到。
• 最后，只要遍历 $2^k$ 次，查看map是否都记录好了这些产品，没有则返回false

时间复杂度

• 遍历一次二进制字符串， 时间复杂度是 $O(n)$
• 最后检测所有截取到的二进制字符串，时间复杂度是 $O(2^k)$
• 这两步是单独的循环，因此时间复杂度是 $O(max(n, 2^k))$

C++ 代码

class Solution {
public:

    bool map[1 << 20];  // k的最大值是20

    bool hasAllCodes(string s, int k) {

        int n = s.size();
        int t = 0;

        for(int i = 0; i < n; i ++) {
            int num = s[i] - '0';
            t = t * 2 + num;    // 传送带

            t &= (1 << k) - 1;  // 扫描器

            if(i >= k - 1)
                map[t] = true;

        }

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

        return true;
    }
};