文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
长度为k的二进制子串所有取值的集合为[0, sum(k)]，其中sum(k)为1 + 2 + 4 + … + 1 << (k - 1)
我们只需要创建一个长度为sum(k) + 1的数组 f ，其中下标为 i 的元素用来标记字符串中子串取值为 i 是否不存在
我们只需要遍历字符串中所有长度为 k 的子串，然后将其数组 f 中二进制值标记为存在
最后
- 如果数组 f 中存在子串中不存在的二进制值，则结果为false
- 如果数组 f 中子串二进制值都存在，则结果为true
题解代码
impl Solution {pub fn has_all_codes(s: String, k: i32) -> bool {if k as usize >= s.len() {return false;}let s = s.as_bytes();let mut max_val = 0;let mut sum = 0;for i in 0..k as usize {max_val += 1 << i;if s[i] == b'1' {sum += 1 << i;}}let mut f = vec![true; max_val + 1];f[sum] = false;for i in k as usize..s.len() {if s[i - k as usize] == b'1' {sum -= 1;}sum >>= 1;if s[i] == b'1' {sum += 1 << (k - 1);}f[sum] = false;}for ok in f {if ok {return false;}}true}
}
题目链接
https://leetcode.cn/problems/check-if-a-string-contains-all-binary-codes-of-size-k/description/
