题目描述
给你一个二进制字符串 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 * 105s[i] 不是'0' 就是 '1'1 <= k <= 20
解法
方法一：哈希表
首先，对于一个长度为 \(n\) 的字符串 \(s\)，长度为 \(k\) 的子串的个数为 \(n - k + 1\)，如果 \(n - k + 1 < 2^k\)，则一定存在长度为 \(k\) 的二进制串不是 \(s\) 的子串，返回 false。
接下来，我们遍历字符串 \(s\)，将所有长度为 \(k\) 的子串存入集合 \(ss\)，最后判断集合 \(ss\) 的大小是否等于 \(2^k\)。
时间复杂度 \(O(n \times k)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(s\) 的长度。
| class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
n = len(s)
m = 1 << k
if n - k + 1 < m:
return False
ss = {s[i : i + k] for i in range(n - k + 1)}
return len(ss) == m
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public boolean hasAllCodes(String s, int k) {
int n = s.length();
int m = 1 << k;
if (n - k + 1 < m) {
return false;
}
Set<String> ss = new HashSet<>();
for (int i = 0; i < n - k + 1; ++i) {
ss.add(s.substring(i, i + k));
}
return ss.size() == m;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public:
bool hasAllCodes(string s, int k) {
int n = s.size();
int m = 1 << k;
if (n - k + 1 < m) {
return false;
}
unordered_set<string> ss;
for (int i = 0; i + k <= n; ++i) {
ss.insert(move(s.substr(i, k)));
}
return ss.size() == m;
}
};
|
| func hasAllCodes(s string, k int) bool {
n, m := len(s), 1<<k
if n-k+1 < m {
return false
}
ss := map[string]bool{}
for i := 0; i+k <= n; i++ {
ss[s[i:i+k]] = true
}
return len(ss) == m
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | function hasAllCodes(s: string, k: number): boolean {
const n = s.length;
const m = 1 << k;
if (n - k + 1 < m) {
return false;
}
const ss = new Set<string>();
for (let i = 0; i + k <= n; ++i) {
ss.add(s.slice(i, i + k));
}
return ss.size === m;
}
|
方法二：滑动窗口
方法一中，我们存储了所有长度为 \(k\) 的不同子串，子串的处理需要 \(O(k)\) 的时间，我们可以改用滑动窗口，每次添加最新字符时，删除窗口最左边的字符。此过程中用一个整型数字 \(x\) 来存放子串。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(s\) 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
n = len(s)
m = 1 << k
if n - k + 1 < m:
return False
ss = set()
x = int(s[:k], 2)
ss.add(x)
for i in range(k, n):
a = int(s[i - k]) << (k - 1)
b = int(s[i])
x = (x - a) << 1 | b
ss.add(x)
return len(ss) == m
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public boolean hasAllCodes(String s, int k) {
int n = s.length();
int m = 1 << k;
if (n - k + 1 < m) {
return false;
}
boolean[] ss = new boolean[m];
int x = Integer.parseInt(s.substring(0, k), 2);
ss[x] = true;
for (int i = k; i < n; ++i) {
int a = (s.charAt(i - k) - '0') << (k - 1);
int b = s.charAt(i) - '0';
x = (x - a) << 1 | b;
ss[x] = true;
}
for (boolean v : ss) {
if (!v) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public:
bool hasAllCodes(string s, int k) {
int n = s.size();
int m = 1 << k;
if (n - k + 1 < m) {
return false;
}
bool ss[m];
memset(ss, false, sizeof(ss));
int x = stoi(s.substr(0, k), nullptr, 2);
ss[x] = true;
for (int i = k; i < n; ++i) {
int a = (s[i - k] - '0') << (k - 1);
int b = s[i] - '0';
x = (x - a) << 1 | b;
ss[x] = true;
}
return all_of(ss, ss + m, [](bool v) { return v; });
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | func hasAllCodes(s string, k int) bool {
n, m := len(s), 1<<k
if n-k+1 < m {
return false
}
ss := make([]bool, m)
x, _ := strconv.ParseInt(s[:k], 2, 64)
ss[x] = true
for i := k; i < n; i++ {
a := int64(s[i-k]-'0') << (k - 1)
b := int64(s[i] - '0')
x = (x-a)<<1 | b
ss[x] = true
}
for _, v := range ss {
if !v {
return false
}
}
return true
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | function hasAllCodes(s: string, k: number): boolean {
const n = s.length;
const m = 1 << k;
if (n - k + 1 < m) {
return false;
}
let x = +`0b${s.slice(0, k)}`;
const ss = new Set<number>();
ss.add(x);
for (let i = k; i < n; ++i) {
const a = +s[i - k] << (k - 1);
const b = +s[i];
x = ((x - a) << 1) | b;
ss.add(x);
}
return ss.size === m;
}
|