Python DFS easy understanding using memo


  • 6

    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
    

  • 0
    H

    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


  • 1
    W

    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
    

  • 3
    Z
    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%
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.