[Python3] Thinking process, no DP needed
Initial thought: brute force and do exactly what the problem says: \n1. Create a queue of reachable indices starting with 0\n2. While the queue is not empty, pu
Initial thought: brute force and do exactly what the problem says: \n1. Create a queue of reachable indices starting with 0\n2. While the queue is not empty, pull from front of queue, call this i\n3. Let x go from i + minJumps to i + maxJumps, if s[x] == \'0\', add to queue\n4. Repeat till queue is empty or reached end\n5. If reached end return true, if queue empty, return false\n\nWe realize that this solution is O(n^2) since maxJump-minJump can be as big as n. But actually, we are close to the solution: notice that we are repeatedly adding in indices that have been visited.\n\nFor example, consider s = "0100000", minJumps = 2, maxJumps = 6. After the first iteration, we have already put all the relevant indices into the queue. When we visit index 2, we can start adding the next reachable indices from where the last iteration leftoff (there are none left in this case). I keep track of where to start with the max_reached variable.\n\nLet n = length of s\nTime complexity: O(n), we visit each index at most twice - once to add to queue, and once to pop it out\nSpace complexity: O(n), in the worst case we can have almost all of the indices of s in the queue at once. For example s = "0000000", minJumps = 1, maxJumps = 6. After one iteration, queue = [1,2,3,4,5,6]\n\n```\nclass Solution:\n    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n        q, max_reached = collections.deque([0]), 0\n        while q:\n            curr_i = q.popleft()\n            if curr_i == len(s) - 1:\n                return True\n            start = max(curr_i + minJump, max_reached + 1)\n            for i in range(start, min(curr_i + maxJump + 1, len(s))):\n                if s[i] == \'0\':\n                    q.append(i)\n            max_reached = curr_i + maxJump\n        return False\n\n```
[]