LEETCODE 1461. Check If a String Contains All Binary Codes of Size K 解题思路分析

题目大意：

检查一个字符串是否包含所有长度为 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 = "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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1461

解题思路分析：

题目的问题是所有长度为k的二进制串是否都是s的子串。如果使用暴力方式遍历每一个二进制字符串，然后再去与s进行contains操作的话，大概率会超时。本题我们需要换一个角度去思考，首先所有长度为k的二进制串一定都是不重复的，因为这些二进制串分别代表了数字0到长度为k的最大二进制数（k个1）。那么我们只要判断一下s中所有长度为k并且不重复的子串个数是否等于长度为k的最大二进制数加一即可（加一的目的是包含二进制数0）。统计s中长度为k的不重复子串很简单，我们使用Set类来排重，然后循环一遍s中所有长度为k的区间，将区间内的子串加入Set即可。

实现代码：

public boolean hasAllCodes(String s, int k) {
    if(k>s.length()) return false; // 如果k大于字符串s的长度，返回false
    // 长度为k的子串
    StringBuilder sb=new StringBuilder();
    // 保存所有不重复的子串
    Set<String> set=new HashSet<>();
    // 为了提高效率，将字符串转为字符数组
    char[] arr=s.toCharArray();
    // 得到第一个长度为k的子串
    for(int i=0;i<k;i++){
        sb.append(arr[i]);
    }
    // 加入set
    set.add(sb.toString());
    // 循环后续所有长度为k的子串
    for(int i=k;i<s.length();i++){
        // 删除原子串首字符，再在尾部加上一个新字符
        sb.deleteCharAt(0).append(arr[i]);
        set.add(sb.toString());  // 加入set
    }
    // 查看set中元素数量是否等于长度为k的二进制串数量
    return set.size()==(1<<k);
}

本题解法执行时间为153ms。

Runtime: 153 ms, faster than 47.34% of Java online submissions for Check If a String Contains All Binary Codes of Size K.

Memory Usage: 56.2 MB, less than 100.00% of Java online submissions for Check If a String Contains All Binary Codes of Size K.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1461-check-if-a-string-contains-all-binary-codes-of-size-k-解题思路分析/