Bit Manipulation
Hash Table
String
Hash Function
Rolling Hash
Description
Given a binary string s
and an integer k
, return true
if every binary code of length k
is a substring of s
. Otherwise, return false
.
Example 1:
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
Example 2:
Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.
Example 3:
Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and does not exist in the array.
Constraints:
1 <= s.length <= 5 * 105
s[i]
is either '0'
or '1'
.
1 <= k <= 20
Solutions
Solution 1
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def hasAllCodes ( self , s : str , k : int ) -> bool :
if len ( s ) - k + 1 < ( 1 << k ):
return False
vis = [ False ] * ( 1 << k )
num = int ( s [: k ], 2 )
vis [ num ] = True
for i in range ( k , len ( s )):
a = ( ord ( s [ i - k ]) - ord ( '0' )) << ( k - 1 )
b = ord ( s [ i ]) - ord ( '0' )
num = (( num - a ) << 1 ) + b
vis [ num ] = True
return all ( v for v in vis )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public boolean hasAllCodes ( String s , int k ) {
int n = s . length ();
if ( n - k + 1 < ( 1 << k )) {
return false ;
}
boolean [] vis = new boolean [ 1 << k ] ;
int num = Integer . parseInt ( s . substring ( 0 , k ), 2 );
vis [ num ] = true ;
for ( int i = k ; i < n ; ++ i ) {
int a = ( s . charAt ( i - k ) - '0' ) << ( k - 1 );
int b = s . charAt ( i ) - '0' ;
num = ( num - a ) << 1 | b ;
vis [ num ] = true ;
}
for ( boolean v : vis ) {
if ( ! v ) {
return false ;
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
bool hasAllCodes ( string s , int k ) {
int n = s . size ();
if ( n - k + 1 < ( 1 << k )) return false ;
vector < bool > vis ( 1 << k );
int num = stoi ( s . substr ( 0 , k ), nullptr , 2 );
vis [ num ] = true ;
for ( int i = k ; i < n ; ++ i ) {
int a = ( s [ i - k ] - '0' ) << ( k - 1 );
int b = s [ i ] - '0' ;
num = ( num - a ) << 1 | b ;
vis [ num ] = true ;
}
for ( bool v : vis )
if ( ! v ) return false ;
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 func hasAllCodes ( s string , k int ) bool {
n := len ( s )
if n - k + 1 < ( 1 << k ) {
return false
}
vis := make ([] bool , 1 << k )
num := 0
for i := 0 ; i < k ; i ++ {
num = num << 1 | int ( s [ i ] - '0' )
}
vis [ num ] = true
for i := k ; i < n ; i ++ {
a := int ( s [ i - k ] - '0' ) << ( k - 1 )
num = ( num - a ) << 1 | int ( s [ i ] - '0' )
vis [ num ] = true
}
for _ , v := range vis {
if ! v {
return false
}
}
return true
}
GitHub