1461.检查一个字符串是否包含所有长度为 K 的二进制子串：哈希表存放所有长度为k的子串

【LetMeFly】1461.检查一个字符串是否包含所有长度为 K 的二进制子串：哈希表存放所有长度为k的子串

力扣题目链接：https://leetcode.cn/problems/check-if-a-string-contains-all-binary-codes-of-size-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 * 105
• s[i] 不是'0' 就是 '1'
• 1 <= k <= 20

解题方法：暴力枚举

使用一个哈希表，存放所有长度为$k$的子串。

最后看看哈希表中子串数量是否等于$2^k$。

• 时间复杂度$O((len(s) - k)\times k)$
• 空间复杂度$O((len(s) - k)\times k)$

AC代码

C++

/*
 * @LastEditTime: 2026-02-23 11:37:10
 */
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> ma;
        for (int i = 0, to = s.size() - k + 1; i < to; i++) {
            ma.insert(s.substr(i, k));
        }
        return ma.size() == (1 << k);
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源