class Solution {
public:
bool hasAllCodes(string s, int k) {
}
};
1461. 检查一个字符串是否包含所有长度为 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 = "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原站题解
cpp 解法, 执行用时: 164 ms, 内存消耗: 49.3 MB, 提交时间: 2022-12-18 14:03:54
class Solution {
public:
bool hasAllCodes(string s, int k) {
if (s.size() < (1 << k) + k - 1) {
return false;
}
int num = stoi(s.substr(0, k), nullptr, 2);
unordered_set<int> exists = {num};
for (int i = 1; i + k <= s.size(); ++i) {
num = (num - ((s[i - 1] - '0') << (k - 1))) * 2 + (s[i + k - 1] - '0');
exists.insert(num);
}
return exists.size() == (1 << k);
}
};
python3 解法, 执行用时: 592 ms, 内存消耗: 35.2 MB, 提交时间: 2022-12-18 14:03:42
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) < (1 << k) + k - 1:
return False
num = int(s[:k], base=2)
exists = set([num])
for i in range(1, len(s) - k + 1):
num = (num - ((ord(s[i - 1]) - 48) << (k - 1))) * 2 + (ord(s[i + k - 1]) - 48)
exists.add(num)
return len(exists) == (1 << k)
java 解法, 执行用时: 53 ms, 内存消耗: 59.5 MB, 提交时间: 2022-12-18 14:03:31
class Solution {
public boolean hasAllCodes(String s, int k) {
if (s.length() < (1 << k) + k - 1) {
return false;
}
int num = Integer.parseInt(s.substring(0, k), 2);
Set<Integer> exists = new HashSet<Integer>();
exists.add(num);
for (int i = 1; i + k <= s.length(); ++i) {
num = (num - ((s.charAt(i - 1) - '0') << (k - 1))) * 2 + (s.charAt(i + k - 1) - '0');
exists.add(num);
}
return exists.size() == (1 << k);
}
}
java 解法, 执行用时: 156 ms, 内存消耗: 65.4 MB, 提交时间: 2022-12-18 13:58:26
class Solution {
public boolean hasAllCodes(String s, int k) {
if (s.length() < (1 << k) + k - 1) {
return false;
}
Set<String> exists = new HashSet<String>();
for (int i = 0; i + k <= s.length(); ++i) {
exists.add(s.substring(i, i + k));
}
return exists.size() == (1 << k);
}
}
python3 解法, 执行用时: 412 ms, 内存消耗: 46.5 MB, 提交时间: 2022-12-18 13:58:06
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) < (1 << k) + k - 1:
return False
exists = set(s[i:i+k] for i in range(len(s) - k + 1))
return len(exists) == (1 << k)
cpp 解法, 执行用时: 500 ms, 内存消耗: 82.4 MB, 提交时间: 2022-12-18 13:57:46
class Solution {
public:
bool hasAllCodes(string s, int k) {
if (s.size() < (1 << k) + k - 1) {
return false;
}
unordered_set<string> exists;
for (int i = 0; i + k <= s.size(); ++i) {
exists.insert(move(s.substr(i, k)));
}
return exists.size() == (1 << k);
}
};