1016.子串能表示从1到N数字的二进制串

链接：1016.子串能表示从1到N数字的二进制串
难度：Medium
标签：字符串
简介：给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。

题解 1 - rust

• 编辑时间：2023-05-11
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn query_string(s: String, n: i32) -> bool {
        for num in 1..=n {
            let snum = format!("{:b}", num);
            if !s.contains(&snum) {
                return false;
            }
        }
        true
    }
}

题解 2 - cpp

• 编辑时间：2023-05-11
• 执行用时：4ms
• 内存消耗：6.3MB
• 编程语言：cpp
• 解法介绍：对于s统计所有出现的数字。

class Solution {
public:
    bool queryString(string s, int n) {
        unordered_set<int> sset;
        int len = s.size();
        for (int i = 0; i < len; i++) {
            int num = 0;
            for (int j = i; j < len && j - i + 1 < 32; j++) {
                num = (num << 1) | (s[j] - '0');
                if (num <= n) sset.insert(num);
                else break;
            }
        }
        sset.erase(0);
        return sset.size() == n;
    }
};

题解 3 - cpp

• 编辑时间：2023-05-11
• 内存消耗：6.1MB
• 编程语言：cpp
• 解法介绍：对于所有n计算二进制字符串是否存在s里。

class Solution {
public:
    bool queryString(string s, int n) {
        for (int num = 1; num <= n; num++) {
            string bin = bitset<32>(num).to_string(); 
            bin = bin.substr(bin.find('1'));
            if (s.find(bin) == string::npos) return false;
        }
        return true;
    }
};

题解 4 - python

• 编辑时间：2023-05-11
• 执行用时：52ms
• 内存消耗：16.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        return all(bin(num)[2:] in s for num in range(1, n + 1))