目录

• 题目描述：
• 示例 1：
• 示例 2：
• 解法：

题目描述：

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

示例 1：

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

示例 2：

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

提示：

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

---

解法：

class Solution {
public:
    string itoa(int num){
        string res = "";
        while(num > 0){
            res = char(num%2 + '0') + res;
            num /= 2;
        }
        return res;
    }
    
    bool contains(string& S, string& s){
        int sz = S.size();
        int len = s.size();
        for(int i = len; i <= sz; i++){
            if(S.substr(i-len, len) == s){
                return true;
            }
        }
        return false;
    }
    
    bool queryString(string S, int N) {
        // 1010 100 10 1
        // 111
        // 110  11
        // 101
        int val = 1;
        while(val <= N){
            val <<= 1;
        }
        val >>= 1;
        for(int i = N; i >= val; i--){
            string s = itoa(i);
            if(contains(S, s) == false){
                return false;
            }
        }
        return true;
    }
};