1016. Binary String With Substrings Representing 1 To N

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.

1
2
3
4
Example 1:

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

1
2
3
4
Example 2:

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

Note:

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

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public boolean queryString(String S, int N) {
        for (int i = 1; i <= N; i++) {
            String binary = Integer.toBinaryString(i);
            
            if (!searchRK(S, binary)) {
                return false;
            }
            
        }
        return true;
    }
    
    boolean search(String s, String p) {
        return s.contains(p);
    }
    
    boolean searchRK(String s, String p) {
        int n = s.length();
        int m = p.length();
        int x = 3;
        
        int ht = hash(p, 0, m, x, m);
        int hs = hash(s, 0, m, x, m);
        
        for (int i = 0; i < n - m; i++) {
            if (hs == ht) {
                return true;
            }
            hs = (hs * x - code(s, i) * pow(x, m) + code(s, i + m));
        }
        
        return ht == hs;
    }
    
    int code(String s, int i) {
        return s.charAt(i) - '0';
    }
    
    static int pow(int a, int b) {
        return (int) Math.pow(a, b);
    }
    
    int hash(String str, int s, int e, int x, int m) {
        int h = 0;
        int degree = m - 1;
        for (int i = s; i < e; i++) {
            h = h + code(str, i) * pow(x, degree);
            degree--;
        }
        return h;
    }
}

Solution#

Solution