Python DFS 45 ms beat 100.00% so far


  • 0
    M

    Very straight forward DFS. The only trick is that k3>k2>k1, so we should check k3 first.

    "You are here!
    Your runtime beats 100.00 % of python submissions."

    39 / 39 test cases passed.
    Status: Accepted
    Runtime: 45 ms
    Submitted: 0 minutes ago

    def dfs(mapp,jump,current,maximum):
        if maximum==current:
            return True
        k1=current+jump-1
        k2=current+jump
        k3=current+jump+1
        if str(k3) in mapp:
            if dfs(mapp,jump+1,k3,maximum):
                return True
        if jump>0 and str(k2) in mapp:
            if dfs(mapp,jump,k2,maximum):
                return True    
        if jump>0 and str(k1) in mapp:
            if dfs(mapp,jump-1,k1,maximum):
                return True
         
        
        return False
    
    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            mapp={}
            maximum=0
            for i in range(1,len(stones)):
                if stones[i]>2*stones[i-1]+1:
                    return False
            for i in range(0,len(stones)): 
                mapp[str(stones[i])]=1
                
            return dfs(mapp,0,0,stones[-1])
    

Log in to reply
 

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