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

解题思路

把每个数字转为二进制字符串，然后判断是否为S的子串。

实现代码

class Solution {
    public boolean queryString(String S, int N) {
        for (int i = 0; i <= N; i++) {
            String binaryString = numToBinaryString(i);
            if (!S.contains(binaryString)) {
                return false;
            }
        }
        return true;
    }

    private String numToBinaryString(int num) {
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            sb.append(num & 1);
            num >>= 1;
        }

        if (sb.length() == 0) {
            sb.append('0');
        }
        return sb.reverse().toString();
    }
}

/*
Runtime: 1 ms, faster than 100.00% of Java online submissions for Binary String With Substrings Representing 1 To N.
Memory Usage: 35.4 MB, less than 100.00% of Java online submissions for Binary String With Substrings Representing 1 To N.
*/