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

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举检查

1. 📝 题目描述

• leetcode

给定一个二进制字符串 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

2. 🎯 s.1 - 枚举检查

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {string} s
 * @param {number} n
 * @return {boolean}
 */
var queryString = function (s, n) {
  for (let i = 1; i <= n; i++) {
    if (!s.includes(i.toString(2))) return false
  }
  return true
}

• 时间复杂度：$O(n\cdot m)$，其中 $m$ 是字符串 $s$ 的长度
• 空间复杂度：$O(\log n)$，存储二进制表示

算法思路：

• 枚举 [1, n] 中的每个整数，将其转换为二进制字符串
• 检查该二进制字符串是否是 s 的子串
• 由于 s 长度最多 1000，实际 n 不会太大，枚举即可