[Python] BFS + Pruning: Maintain the Farthest Boundary
Idea\nAn intuitive idea is search s using BFS and maintaining a visited array. However, since there are so many overlaps fo the next step of nearby start points
**Idea**\nAn intuitive idea is search `s` using BFS and maintaining a `visited` array. However, since there are so many overlaps fo the next step of nearby start points, repeatedly checking visited will make the solution slow.\nAn observation is that for each node in BFS, it is only the unvisited positions in the possible next step that matters. Hence, by maintaining a `farthest` position variable, we could easily remove the overlapped, or visited, range for the next step.\n\n**Complexity**\nTime: `O(n)` worst case\nSpace: `O(n)`\n\n**Python**\n```\n    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n        if s[-1] == \'1\':\n            return False\n        \n        n = len(s)\n        q = deque([0])\n        farthest = 0\n        \n        while q:\n            i = q.popleft()\n            for nxt in range(\n                max(i + minJump, farthest + 1), \n                min(i + maxJump, n - 1) + 1\n            ):\n                if s[nxt] == \'0\':\n                    q.append(nxt)\n            farthest = nxt\n            if farthest == n - 1:\n                return True\n        \n        return False\n```
['Breadth-First Search', 'Python']