当前位置：首页 > article >正文

Rust 力扣 - 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

article 2024/11/5 11:42:47

文章目录

题目描述
题解思路
题解代码
题目链接

题目描述

在这里插入图片描述

题解思路

长度为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
    }
}