Description#
Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.
Example 1:
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
Example 2:
Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.
Example 3:
Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and does not exist in the array.
Constraints:
1 <= s.length <= 5 * 105s[i] is either '0' or '1'.1 <= k <= 20
Solutions#
Solution 1#
1
2
3
4
| class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
ss = {s[i : i + k] for i in range(len(s) - k + 1)}
return len(ss) == 1 << k
|
1
2
3
4
5
6
7
8
9
| class Solution {
public boolean hasAllCodes(String s, int k) {
Set<String> ss = new HashSet<>();
for (int i = 0; i < s.length() - k + 1; ++i) {
ss.add(s.substring(i, i + k));
}
return ss.size() == 1 << k;
}
}
|
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<string> ss;
for (int i = 0; i + k <= s.size(); ++i) {
ss.insert(move(s.substr(i, k)));
}
return ss.size() == 1 << k;
}
};
|
1
2
3
4
5
6
7
| func hasAllCodes(s string, k int) bool {
ss := map[string]bool{}
for i := 0; i+k <= len(s); i++ {
ss[s[i:i+k]] = true
}
return len(ss) == 1<<k
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) - k + 1 < (1 << k):
return False
vis = [False] * (1 << k)
num = int(s[:k], 2)
vis[num] = True
for i in range(k, len(s)):
a = (ord(s[i - k]) - ord('0')) << (k - 1)
b = ord(s[i]) - ord('0')
num = ((num - a) << 1) + b
vis[num] = True
return all(v for v in vis)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean hasAllCodes(String s, int k) {
int n = s.length();
if (n - k + 1 < (1 << k)) {
return false;
}
boolean[] vis = new boolean[1 << k];
int num = Integer.parseInt(s.substring(0, k), 2);
vis[num] = true;
for (int i = k; i < n; ++i) {
int a = (s.charAt(i - k) - '0') << (k - 1);
int b = s.charAt(i) - '0';
num = (num - a) << 1 | b;
vis[num] = true;
}
for (boolean v : vis) {
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
| class Solution {
public:
bool hasAllCodes(string s, int k) {
int n = s.size();
if (n - k + 1 < (1 << k)) return false;
vector<bool> vis(1 << k);
int num = stoi(s.substr(0, k), nullptr, 2);
vis[num] = true;
for (int i = k; i < n; ++i) {
int a = (s[i - k] - '0') << (k - 1);
int b = s[i] - '0';
num = (num - a) << 1 | b;
vis[num] = true;
}
for (bool v : vis)
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
22
23
| func hasAllCodes(s string, k int) bool {
n := len(s)
if n-k+1 < (1 << k) {
return false
}
vis := make([]bool, 1<<k)
num := 0
for i := 0; i < k; i++ {
num = num<<1 | int(s[i]-'0')
}
vis[num] = true
for i := k; i < n; i++ {
a := int(s[i-k]-'0') << (k - 1)
num = (num-a)<<1 | int(s[i]-'0')
vis[num] = true
}
for _, v := range vis {
if !v {
return false
}
}
return true
}
|
