题目如下:
Given a binary string
S
(a string consisting only of ‘0’ and ‘1’s) and a positive integerN
, 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: trueExample 2:
Input: S = "0110", N = 4
Output: falseNote:
1 <= S.length <= 1000
1 <= N <= 10^9
解题思路:最初我的想法是判断1~N是否存在于S中,但是这样效率太低。思路转换一下,判断S中能否组成从1~N中所有的数即可,
代码如下:
class Solution(object):
def queryString(self, S, N):
"""
:type S: str
:type N: int
:rtype: bool
"""
dic = {}
for i in range(len(S)-1,-1,-1):
power = 0
amount = 0
for j in range(i,-1,-1):
if S[j] == '':
power += 1
continue
tmp = amount + pow(2, power)
if tmp > N:
break
dic[tmp] = 1
power += 1
amount = tmp
return len(dic) == N