Following is my backtracking solution using dict for memorization.
The memo dict is using for save those dead end. So when we get to the same stone with the same speed we don't need to search further.
class Solution(object): def canCross(self, stones): self.memo = set() target = stones[-1] stones = set(stones) res = self.bt(stones, 1, 1, target) return res def bt(self, stones, cur, speed, target): # check memo if (cur, speed) in self.memo: return False if cur==target: return True if cur>target or cur<0 or speed<=0 or cur not in stones: return False # dfs candidate = [speed-1, speed, speed+1] for c in candidate: if (cur + c) in stones: if self.bt(stones, cur+c, c, target): return True self.memo.add((cur,speed)) return False
Like this solution. It is also slightly faster than the other python solution: https://discuss.leetcode.com/topic/59570/python-documented-solution-that-is-easy-to-understand
Good solution. Upvoted! I cleaned up the code by removing some redundant condition checking, e.g.,
if cur>target or cur<0 and
if (cur+c) in stones.
class Solution(object): def canCross(self, stones): """ :type stones: List[int] :rtype: bool """ target, stones, memo = stones[-1], set(stones), set() return self.backtrack(stones, 1, 1, target, memo) def backtrack(self, stones, pos, jump, target, memo): if (pos, jump) in memo: return False if pos == target: return True if jump <= 0 or pos not in stones: return False for j in (jump-1, jump, jump+1): if self.backtrack(stones, pos+j, j, target, memo): return True memo.add((pos, jump)) # record bad position and jump return False
class Solution(object): def canCross(self, stones): """ :type stones: List[int] :rtype: bool """ stone_set, fail = set(stones), set() stack = [(0, 0)] while stack: stone, jump = stack.pop() for j in (jump-1, jump, jump+1): s = stone + j if j > 0 and s in stone_set and (s, j) not in fail: if s == stones[-1]: return True stack.append((s, j)) fail.add((stone, jump)) return False # 39 / 39 test cases passed. # Status: Accepted # Runtime: 78 ms # 98.51%
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.