1461. Check If a String Contains All Binary Codes of Size K

Leetcode link

解题思路——哈希表

题目给定一个二进制字符串 s 跟一个数字 k，要求我们判断所有的 k 位二进制是否都是字符串 s 的子串

首先，所有的 k 位二进制总共有 个，一个字符串要包含所有的 k 位二进制，长度不能小于

哈希表的思路是这样的：

• 遍历字符串 s，找出所有长度为 k 的子串
• 将这些子串放到一个哈希表中
• 利用哈希表去重的特性，如果遍历完了之后哈希表的长度等于 则表示所有的 k 位二进制都被我们找到了

C++

class Solution {
public:
    bool hasAllCodes(string s, int k) {
          // reduce computation
        if(s.size() < ((1<<k) + k - 1)){
            return false;
        }

        // speed up substr()
        string_view sv(s);
        unordered_set<string_view> subStrs;
        for(int i=0;i+k<=s.size();i++) {
            subStrs.insert(sv.substr(i, k));
        }
        return subStrs.size() == (1<<k);
    }
};

解题思路——哈希表+滑动窗口

上述思路最大的性能瓶颈在于对字符串的操作，我们可以依靠滑动窗口的思路来减少对字符串的操作

我们假设字符串当前遍历到长度为 k 的二进制子串为：

下一个子串就是：

我们可以把上述两个二进制子串转成十进制的表示为

结合上述两个式子，我们可以得到递推公式：

至此，我们就可以把哈希表的指责从保存字符串变成保存整数了，最重要的是，对字符串的操作少了非常多次

C++

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        if(s.size() < (1<<k) + k - 1) {
            return false;
        }

        int num = stoi(s.substr(0, k), nullptr, 2);
        unordered_set<int> substrs{num};
        for(int i = 1;i+k <= s.size();i++) {
            num = ((num - ((s[i - 1] - '0') << (k - 1))) << 1) + (s[i + k - 1] - '0');
            substrs.insert(num);
        }
        return substrs.size() == (1<<k);
    }
};