Clear DP Python using hashmap and hashset


  • 0
    B

    The dictionary key is the stone and the value is a set that contains the units for each jump that can land on that particular stone.

    class Solution(object):
        def canCross(self, stones):
            """
            :type stones: List[int]
            :rtype: bool
            """
            landings = collections.defaultdict(set)
            landings[1].add(1)
            for i in range(1, len(stones)-1):
                stone = stones[i]
                if stone not in landings:
                    continue
                for k in landings[stone]:
                    for new_k in k-1, k, k+1:
                        if not new_k:
                            continue
                        landings[stone+new_k].add(new_k)
            return stones[-1] in landings
    

Log in to reply
 

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