题目描述
给你一个二进制字符串 s
和一个整数 k
。
如果所有长度为 k
的二进制字符串都是 s
的子串,请返回 True
,否则请返回 False
。
样例
输入:s = "00110110", k = 2
输出:true
解释:长度为 2 的二进制串包括 "00","01","10" 和 "11"。
它们分别是 s 中下标为 0,1,3,2 开始的长度为 2 的子串。
输入:s = "00110", k = 2
输出:true
输入:s = "0110", k = 1
输出:true
解释:长度为 1 的二进制串包括 "0" 和 "1",显然它们都是 s 的子串。
输入:s = "0110", k = 2
输出:false
解释:长度为 2 的二进制串 "00" 没有出现在 s 中。
输入:s = "0000000001011100", k = 4
输出:false
提示:
1 <= s.length <= 5 * 10^5
s
中只含0
和1
。1 <= k <= 20
算法分析
- 1、将字符串中长度是
k
的字符段对应的十进制整数存在Set
中 - 2、从
0
枚举到1 << k
的整数,即长度为K
的二进制子串,判断是否所有整数都在Set
中存在过,若均存在返回true
,否则返回false
时间复杂度 $O(n + 2^k)$
n表示字符串长度,k表示二进制子串长度
Java 代码
class Solution {
static int get(String t)
{
int res = 0;
int k = 1;
for(int i = t.length() - 1;i >= 0;i --)
{
if(t.charAt(i) == '1') res += k;
k <<= 1;
}
return res;
}
public boolean hasAllCodes(String s, int k) {
HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0;i + k <= s.length();i ++)
{
String t = s.substring(i,i + k);
set.add(get(t));
}
for(int i = 0;i < 1 << k;i ++)
{
if(!set.contains(i)) return false;
}
return true;
}
}
固定长度的双指针遍历字符串 看看最后收集到的子串数目是不是所有排列组合的数目。
这种思路 速度不快 但是代码挺短的
嗯嗯,简洁代码,谢谢大佬指点,
不敢,不敢,这代码效率挺低了. 向大佬学习!!!
大佬谦虚了哈哈