Weekly Contest 129--1023. Binary String With Substrings Representing 1 To N--Medium

Given a binary string S (a string consisting only of '0' and '1's) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input: S = "0110", N = 3
Output: true
Example 2:

Input: S = "0110", N = 4
Output: false

Note:

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

1.思考

• 先将数字转化为二进制字符串，然后进行比较，先简单比较首字母，再看整体是否相等。
• 其实比较是否相等时有比较简便的算法的，可以再研究研究。
  
  

2.实现

class Solution {
public:
    bool queryString(string S, int N) {   
        int ls = S.size();
        string ns;
        bool flag = false;
        for(int num=1; num<=N; num++){
            ns = DecimalToBinary(num);
            //Compare
            flag = false;
            int ln = ns.size();
            for(int i=0; i<=ls-ln; i++){
                if(S[i]==ns[0] && S.substr(i,ln)==ns){
                    flag = true;
                    break;
                }
            }
            if(flag == false)
                return false;
        }
        return true;        
    }
    
    //Decimal to Binary
    string DecimalToBinary(int N)
    {
        string ns;
        while(N){
            if(N%2)
                ns = "1" + ns;
            else                
                ns = "0" + ns;
            N = N/2;
        }
        return ns;        
    }
};