Medium

题目描述

给定一个二进制字符串 s 和一个正整数 n，如果范围 [1, n] 中所有整数的二进制表示都是 s 的子串，则返回 true，否则返回 false。

子串是字符串中连续的字符序列。

示例 1：

输入：s = "0110", n = 3
输出：true

示例 2：

输入：s = "0110", n = 4
输出：false

约束条件：

  • 1 <= s.length <= 1000
  • s[i] 是 '0' 或 '1'
  • 1 <= n <= 10^9

提示：

  • 我们只需要检查长度最多为 30 的子串，因为 10^9 有 30 位。

解题思路

解题思路

这道题要求检查1到n的所有数字的二进制表示是否都是字符串s的子串。看似需要检查n个数字，但实际上可以通过以下优化来解决：

关键观察

  1. 位数限制：由于n最大为10^9，而2^30 > 10^9，所以我们只需要考虑长度不超过30的二进制串。

  2. 反向思考：与其检查1到n是否都在s中，不如遍历s的所有可能子串，看能找到多少个有效的数字。

  3. 长度优化：对于长度为k的二进制串，最多只有2^k个不同的数值。当k较大时，s中长度为k的子串数量可能远小于2^k，这时很可能无法覆盖所有需要的数字。

算法步骤

  1. 使用HashSet存储所有在s中找到的数字
  2. 遍历s的所有子串，将合法的二进制数字（不以0开头，除非是"0"本身）加入集合
  3. 检查集合是否包含1到n的所有数字

时间复杂度优化

由于字符串长度最大1000，理论上需要检查的子串数量为O(L²)，但实际上：

  • 我们只关心能转换为1到n范围内数字的子串
  • 对于长度超过log₂(n)的子串，大部分都会超出范围
  • 可以提前终止不必要的计算

这个方法的优势是避免了逐一生成1到n的二进制表示，而是直接从字符串中提取所有可能的数字。

代码实现

class Solution {
public:
    bool queryString(string s, int n) {
        if (n >= 1000) {
            // 当n很大时，不太可能在长度1000的字符串中找到所有数字
            return false;
        }
        
        unordered_set<int> found;
        int len = s.length();
        
        for (int i = 0; i < len; i++) {
            if (s[i] == '0') continue; // 跳过以0开头的数字
            
            int num = 0;
            for (int j = i; j < len && j - i < 32; j++) {
                num = num * 2 + (s[j] - '0');
                if (num > n) break;
                if (num > 0) {
                    found.insert(num);
                }
            }
        }
        
        return found.size() == n;
    }
};

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        if n >= 1000:
            return False
            
        found = set()
        length = len(s)
        
        for i in range(length):
            if s[i] == '0':
                continue
                
            num = 0
            for j in range(i, min(i + 32, length)):
                num = num * 2 + int(s[j])
                if num > n:
                    break
                if num > 0:
                    found.add(num)
        
        return len(found) == n

public class Solution {
    public bool QueryString(string s, int n) {
        if (n >= 1000) {
            return false;
        }
        
        HashSet<int> found = new HashSet<int>();
        int len = s.Length;
        
        for (int i = 0; i < len; i++) {
            if (s[i] == '0') continue;
            
            int num = 0;
            for (int j = i; j < len && j - i < 32; j++) {
                num = num * 2 + (s[j] - '0');
                if (num > n) break;
                if (num > 0) {
                    found.Add(num);
                }
            }
        }
        
        return found.Count == n;
    }
}

var queryString = function(s, n) {
    if (n >= 1000) {
        return false;
    }
    
    const found = new Set();
    const len = s.length;
    
    for (let i = 0; i < len; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(L × min(L, 32))，其中 L 是字符串长度。外层循环 O(L)，内层循环最多32次
空间复杂度O(min(n, L×32))，用于存储找到的数字集合