Description
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.
给定一个二进制字符串 S（一个仅由若干 ‘0’ 和 ‘1’ 构成的字符串）和一个正整数 N，如果对于从 1 到 N 的每个整数 X，其二进制表示都是 S 的子串，就返回 true，否则返回 false。
题目链接：https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/
Difficulty: medium
Example 1:
Input: S = "0110", N = 3
Output: true
Example 2:
Input: S = "0110", N = 4
Output: false
Note:
- 1 <= S.length <= 1000
- 1 <= N <= 10^9
分析
- 如下实现了KMP字符串匹配算法，将每个数转换成二进制的字符串表示形式；
- 所有的结果与S比较，若全部匹配返回True；
- 反之返回False；
- 备注：二进制可以用bin(N)得到，匹配也可以直接用in判断，当时担心时间复杂度太高，想多了。
参考代码
class Solution(object):
def queryString(self, S, N):
def getNext(p):
ne=[-1]*len(p)
j = 0
k = -1
while (j < len(p) - 1):
if (k == -1 or p[k] == p[j]):
j+=1
k+=1
ne[j] = k
else:
k = ne[k]
return ne
def KMP(s,p):
ne=getNext(p)
i=0
j=0
while (i < len(s) and j < len(p)):
if (j == -1 or s[i] == p[j]):
i+=1
j+=1
else:
j = ne[j]
if (j == len(p)):
return True
else:
return False
def getN(N):
n=''
while(N > 0):
if(N%2==0):
n='0'+n
else:
n='1'+n
N//=2
return n
return all(KMP(S,getN(i)) for i in range(N, N / 2, -1))