Share my python solution


  • 0
    N

    I initially wrote a bottom-up DP, but got the TLE. So I switched to DFS with memorization and it worked. Haven't really thought about how to clean it up yet.

        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            def canCrossHelper(dp, i, step):
                if (i, step) in dp:
                    return dp[(i, step)]
                if i == len(stones) - 1:
                    dp[(i, step)] = True
                    return True
                j = i + 1
                while j < len(stones) and stones[j] <= stones[i] + step + 1:
                    if stones[j] - stones[i] in [step - 1, step, step + 1] and canCrossHelper(dp, j, stones[j] - stones[i]):
                        dp[(i, step)] = True
                        return True
                    j += 1
                dp[(i, step)] = False
                return False
            
            if len(stones) == 1:
                return True
            if stones[1] != 1:
                return False
            return canCrossHelper({}, 1, 1)
    

Log in to reply
 

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