Advertisement
Iam_Sandeep

Jump Game 7

Jul 15th, 2022 (edited)
1,029
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.43 KB | None | 0 0
  1. #1.BFS
  2. class Solution:
  3.     def canReach(self, s: str, mx: int, my: int) -> bool:
  4.         q=deque()
  5.         far=0
  6.         n=len(s)
  7.         q.append(0)
  8.         while q:
  9.             t=q.popleft()
  10.             if t==n-1:return True
  11.             for x in range(max(t+mx,far+1),min(n,t+my+1)):
  12.                 if s[x]!='1':
  13.                     q.append(x)
  14.                     if x==n-1:return True
  15.             far=t+my
  16.         return False
  17.  '''  
  18. Here reach tells how many starting points in the current sliding window helped you to reach current index  
  19. 2.DP+SLIDING WINDOW'''
  20. class Solution:
  21.     def canReach(self, s: str, mx: int, my: int) -> bool:
  22.         n=len(s)
  23.         dp=[False]*n
  24.         reach=0 #reachable zeroes
  25.         dp[0]=(s[0]=='0')
  26.         for i in range(1,n):
  27.             #at index i window will be from i-maxjumps,i-minjumps
  28.             if i>=mx:#if i-mx is +ve if dp[i-mx] is reachable
  29.                 reach = reach+(1 if dp[i-mx] else 0)#why we are adding? Because ith index is added to our sliding window.
  30.             if i>my:
  31.                 reach = reach-(1 if dp[i-my-1] else 0) #why we substract because we are leaving i-maxjumps index from our sliding window
  32.             if s[i]=='0' and reach>0:#If current value at index is 0 and if reachable 0s are >0 then we can reach from sliding window (i-maxjumps,i-minjumps)
  33.                 dp[i]=True
  34.             else:
  35.                 dp[i]=False
  36.         return dp[-1]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement