力扣每日一题 20260223

467 words

2 minutes

力扣每日一题 20260223

2026-02-23

leetcode

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

看了下数据范围感觉很宽，我们可以用暴力枚举的做法。

首先考虑长度为 $k$ 的 $01$ 字符串有 $2^k$ 种，所以我们可以枚举字符串 $s$ 的所有长度为 $k$ 的字串，丢到哈希表里，最后看哈希表里有没有 $2^k$ 个元素就好了，复杂度 $O((n-k)k)$ 。

代码：

1
class Solution {
2
public:
3
    bool hasAllCodes(string s, int k) {
4
        if (s.size() < k) return false;
5
        unordered_map<int, int> mp;
6
        for (int i = 0; i <= s.size() - k; i++) {
7
            int x = stoi(s.substr(i, k), nullptr, 2);
8
            mp[x] = 1;
9
        }
10
        if (mp.size() == (1 << k)) return true;
11
        else return false;
12
    }
13
};

上面是最简单粗暴的做法，我们可以在循环里加一个剪枝，如果提前找到了 $2^k$ 种子串就直接返回掉。

代码：

1
class Solution {
2
public:
3
    bool hasAllCodes(string s, int k) {
4
        if (s.size() < k) return false;
5
        unordered_map<int, int> mp;
6
        for (int i = 0; i <= s.size() - k; i++) {
7
            int x = stoi(s.substr(i, k), nullptr, 2);
8
            mp[x] = 1;
9
            //这里喵↓
10
            if (mp.size() == (1 << k)) return true;
11
        }
12
        if (mp.size() == (1 << k)) return true;
13
        else return false;
14
    }
15
};

再继续想，考虑到我们枚举每个子串是不是很像滑动窗口，那我们完全没必要用 $O(k)$ 的复杂度去取子串，我们只需要在枚举下一个子串的时候减掉丢下去那位，加上新进来的那位（通过左右移就可以实现），这样我们能剩一个 $O(k)$ 的复杂度，把复杂度降到 $O(n)$ 。

代码：

1
class Solution {
2
public:
3
    bool hasAllCodes(string s, int k) {
4
        if (s.size() < k) return false;
5
        int mask = (1 << k) - 1, x = 0;
6
        unordered_map<int, int> mp;
7
        for (int i = 0; i < s.size(); i++) {
8
            x = (x << 1 & mask) | (s[i] & 1);
9
            if (i + 1 >= k) mp[x] = 1;
10
            if (mp.size() == (1 << k)) return true;
11
        }
12
        if (mp.size() == (1 << k)) return true;
13
        else return false;
14
    }
15
};