String
Description
Given a binary string s
and a positive integer n
, return true
if the binary representation of all the integers in the range [1, n]
are substrings of s
, or false
otherwise .
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "0110", n = 3
Output: true
Example 2:
Input: s = "0110", n = 4
Output: false
Constraints:
1 <= s.length <= 1000
s[i]
is either '0'
or '1'
.
1 <= n <= 109
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def queryString ( self , s : str , n : int ) -> bool :
if n > 1000 :
return False
return all ( bin ( i )[ 2 :] in s for i in range ( n , n // 2 , - 1 ))
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public boolean queryString ( String s , int n ) {
if ( n > 1000 ) {
return false ;
}
for ( int i = n ; i > n / 2 ; i -- ) {
if ( ! s . contains ( Integer . toBinaryString ( i ))) {
return false ;
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public :
bool queryString ( string s , int n ) {
if ( n > 1000 ) {
return false ;
}
for ( int i = n ; i > n / 2 ; -- i ) {
string b = bitset < 32 > ( i ). to_string ();
b = b . substr ( b . find_first_not_of ( '0' ));
if ( s . find ( b ) == string :: npos ) {
return false ;
}
}
return true ;
}
};
func queryString ( s string , n int ) bool {
if n > 1000 {
return false
}
for i := n ; i > n / 2 ; i -- {
if ! strings . Contains ( s , strconv . FormatInt ( int64 ( i ), 2 )) {
return false
}
}
return true
}
function queryString ( s : string , n : number ) : boolean {
if ( n > 1000 ) {
return false ;
}
for ( let i = n ; i > n / 2 ; -- i ) {
if ( s . indexOf ( i . toString ( 2 )) === - 1 ) {
return false ;
}
}
return true ;
}
GitHub