**解析:**Version 1,使用队列来保存可进行下一次检索的候选索引,从第0
的位置开始检索,根据minJump
和maxJump
确定检索范围,如果当前字符为0
,则将索引添加到队列中,如果恰好是最后一个位置,返回True
。下一次的检索范围不能直接从index+minJump
开始,因为有可能会造成重复检索,因此取max(index+minJump, end)
,end
为上一次检索的最后位置,这样检索的时间复杂度为O(n)
。
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
queue = collections.deque()
queue.append(0)
end = 0
while queue:
index = queue.popleft()
start = max(index+minJump, end)
end = min(index+maxJump+1, len(s))
for i in range(start, end):
if s[i] == '0':
if i == len(s) - 1:
return True
queue.append(i)
return False