X

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-解题思路分析/
Categories: leetcode
kwantong: