Python solution with detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/74652/python-solution-with-detailed-explanation

    Frog Jump https://leetcode.com/problems/frog-jump/

    Memoization: Time: O(N^2) and Space: O(N^2 + N)

    • The problem can be formulated as: Given we are at postiion pos and the previous jump that got us here was k, can we reach the final destination?
    • The state of the problem can be described using the current position (pos) and the previous jump (k) which got us in the current position.
    • Given pos and k, the set of new jumps is (k-1,k,k+1) and the set of new positions is (pos+k-1,pos+k, pos+k+1). If the new jumps are positive and the new positions are valid positions in stone array, we can make potentially three recursive calls.
    • The initial condition is that at start position, the previous jump is 0. The terminating condition is pos == stones[-1].
    • To rapidly test if a new position is valid, we use extra memory and store the valid positions in a set. If we do not want to use additional memory, we can use a linear scan O(N^3) or we can use binary search O(N^2 lg(N)). Otherwise the complexity is ~O(3N^2) which is N^2.
    class Solution(object):
        def helper(self, pos, k, stones, N, cache):
            if pos > N:
                return False
            elif pos == N:
                return True
            elif pos in cache and k in cache[pos]:
                return cache[pos][k]
            else:
                cache.setdefault(pos, {})[k] = False
                for jump in (k-1, k, k+1):
                    if jump > 0 and (pos+jump) in stones:
                        if self.helper(pos+jump, jump, stones, N, cache):
                            cache[pos][k] = True
                            return True
                return False
            
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            return self.helper(stones[0], 0, set(stones), stones[-1], {})
    

    **Dynamic Programming - Time and Space as: O(N^2) **

    • Imagine at position pos, we have the set of jumps that could have brought us to position pos. Then, each of these jumps, can feed three additional jumps and 3 new positions. If at the last stone, there is even a single possible jump that could have brought us there, we know there is a path to the last stone.
    • Say we iterate each of the stone positions in order (lowest to largest) and say we are at position pos. How can we know what jumps could have got us to pos?
    • Maintain a map(stone_map) with key as position and value as a set of possible jumps (pjumps) that could have helped us reach pos. For the first position, we have just 1 pjump as 0. Using a pjump, we can find the potential new jumps (njumps) and then derive the new positions implied by them. If those positions are valid, we can add njump to the set corresponding to their entry in the stone_map
    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            stone_map = {pos:set([]) for pos in stones}
            stone_map[stones[0]].add(0)
            for pos in stones:
                for pjump in stone_map[pos]:
                    for njump in (offset+pjump for offset in [-1,0,1] if offset+pjump > 0):
                        if njump+pos in stone_map:
                            stone_map[njump+pos].add(njump)
            return len(stone_map[stones[-1]]) > 0
    

Log in to reply
 

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