1871. Jump Game VII

class Solution:
    def canReach(self, s: str, a: int, b: int) -> bool:
        """ tc O(N) sc O(N)
        dp[i]: start from idx= 0, there are at least 1 way to jump to s[i-1]        
        """
        n = len(s)
        dp = [0] * (n+1)
        psum = [0] *(n+1)
        dp[1] = 1
        psum[1] = 1
        for i in range(2,n+1):
            # i is next stop  before jump from [l,r]
            if s[i-1] == '0' and i - a >= 1 :#(i-1)-a >=0:
                l = max(1,i-b) 
                r = i - a  
        # means from [i-b,i-a] there at least one case, k   where dp[k] == 1  
                if psum[r]- psum[l-1]>0: 
                    dp[i] = 1
            psum[i] = psum[i-1] + dp[i]
        return dp[n]
                

class Solution:
    def canReach(self, s: str, a: int, b: int) -> bool:  #minJump  a   maxJump b
        """tc O(N) sc O(N)
        """
        mx = 0
        n = len(s)
        q = collections.deque([0]) # 0: start
        while q:
            i = q.popleft()
            l = max(i+a,mx+1)
            r = min(i+b,n-1)
            for j in range(l,r+1):
                if s[j] == '0':
                    if j == n-1: return True
                    q.append(j)
            # mx = max(mx,i+b)
            mx = i + b # it's like topological sort, means mx will always larger while doing BFS 
        return False 

class Solution:
    def canReach(self, s: str, a: int, b: int) -> bool:
        """
        main idea: sliding window  
        tc O(N)  sc O(1)
        """
        n = len(s)
        minv=maxv = 0
        # edge case:
        if s[-1] == '1':
            return False 
        for i in range(n-1):
            if s[i] == '1' or i < minv :
                continue
            if i > maxv:
                return False
            
            if s[i] == '0':
                minv = i+a
                maxv = min(i+b,n-1)
                if minv<=n-1<=maxv:
                    return True 
        return False