Python DFS beats 95%


  • 0
    T

    A drawback for this DFS solution might be the large recursion depth.

    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
    
            if stones[1] > 1: return False
            dp = {x:{} for x in stones}
            def dfs(idx, prev):
            	if idx not in dp: return False
            	if prev in dp[idx]: return dp[idx][prev]
            	res = idx == stones[-1] or (prev > 1 and dfs(idx + prev - 1, prev - 1)) or (prev > 0 and dfs(idx + prev, prev)) or dfs(idx + prev + 1, prev + 1)
            	dp[idx][prev] = res
            	return res
            return dfs(1, 1)
    

Log in to reply
 

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