题目描述

给定一个二进制字符串 S（一个仅由若干 ‘0’ 和 ‘1’ 构成的字符串）和一个正整数 N，如果对于从 1 到 N 的每个整数 X，其二进制表示都是 S 的子串，就返回 true，否则返回 false。

样例

输入：S = "0110", N = 3
输出：true

输入：S = "0110", N = 4
输出：false

注意

• 1 <= S.length <= 1000
• 1 <= N <= 10^9

算法

(子串枚举) $O(S.length)$

• 直接枚举 S 的长度不超过 30 的子串，如果子串构成了 1 到 N 中的数字，则加到一个集合中，最后判断集合的大小是否等于 N。

时间复杂度

• 枚举子串的长度不超过 30，故时间复杂度为 $O(S)$。

空间复杂度

• 需要一个集合来保存出现过的数字，但数字的个数仍然不超过 $30 \times S.length$，故空间复杂度为 $O(S)$。

C++ 代码

class Solution {
public:
    bool queryString(string S, int N) {
        unordered_set<int> vis;
        int n = S.length();
        for (int i = 0; i < n; i++) {
            int t = 0;
            for (int len = 1; i + len <= n; len++) {
                if (len == 31)
                    break;
                t = t * 2 + S[i + len - 1] - '0';
                if (t > N)
                    break;
                if (t > 0 && t <= N)
                    vis.insert(t);
            }
        }

        return vis.size() == N;
    }
};