1871. Jump Game VII - cocoder39/coco39_LC GitHub Wiki

1871. Jump Game VII

Option 1: BFS + pruning

using max(i + minJump, maxCheck + 1) instead of max(i + minJump, len(s)). The former pruning reduces the time complexity to O(n) while the latter is O(n^2)

import collections
class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        queue = collections.deque([0])
        visited, maxCheck = set([0]), 0
        while queue:
            i = queue.popleft()
            for j in range(max(i + minJump, maxCheck + 1), min(i + maxJump + 1, len(s))):
                if s[j] == '0' and j not in visited:
                    if j == len(s) - 1: 
                        return True
                    queue.append(j)
                    visited.add(j)
            maxCheck = max(maxCheck, i + maxJump)
        return False

Option 2: DP + sliding window

each index i is mapped to a range [i-maxJump, i-minJump]

• => if there exists one reachable within the range then i is also reachable
• => using sliding window to tell if there exist one reachable within the range
• => adding i-minJump into window and kick out i-maxJump-1 from window

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        if s[-1] != '0':
            return False
        
        n = len(s)
        dp = [False] * n
        dp[0] = True
        
        count = 0
        for i in range(1, n):
            if i > maxJump and dp[i-maxJump-1]:
                count -= 1
            if i >= minJump and dp[i-minJump]:
                count += 1
            dp[i] = (count > 0 and s[i] == '0')
        
        return dp[-1]