blob: 892a5c5f6dbf1726464f23d1e003adeae7acd411 (
plain)
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
|
# 1016. Binary String With Substrings Representing 1 To N
"""
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.
"""
class Solution(object):
def queryString(self, s, n):
"""
:type s: str
:type n: int
:rtype: bool
"""
if n > len(s) * 2:
return False
l = len(bin(n)) - 2
seen = {s[i : i + l] for i in range(len(s))} | {
s[i : i + l - 1] for i in range(len(s))
}
return all(bin(i)[2:] in seen for i in range(n, n / 2, -1))
if __name__ == "__main__":
obj = Solution()
print(obj.queryString("0110", 3)) # expect: true
print(obj.queryString("0110", 4)) # expect: false
|