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
Solution1:
class Solution {
public boolean queryString(String S, int N) {
/*
for every i <= N/2, the binary string of 2*i will contain binary string of i
*/
for (int i = N; i > N / 2; i --) {
if (!S.contains(Integer.toBinaryString(i))) {
return false;
}
}
return true;
}
}
Solution2:
class Solution {
public boolean queryString(String S, int N) {
/*
suppose that N > 2047 then S must contain substrings of length 11 that represents all 1024 numbers from 1024 to 2047. But it is not possible because S is 1000 long so it can have at most 989 substrings of length 11. So we just need to check if N <= 2047.
*/
if (N >= 2048) return false;
boolean[] nums = new boolean[N];
int count = 0;
for (int i = 0; i < S.length(); i ++) {
if (S.charAt(i) == '0') continue;
for (int j = i, num = 0; j < S.length() && num <= N; j ++) {
num = (num << 1) + S.charAt(j) - '0';
if (num <= N && !nums[num - 1]) {
nums[num - 1] = true;
count ++;
}
}
}
return count == N;
}
}