DP solution in Python using HashMaps and Sets


  • 0
    D

    The idea is to iterate through all stones and to look at k, that is associated with that stone. When we are done iterating through all the stones and k's we just look if the last stone is in our memo HashMap.

    How can I improve it ? Any suggestions ?

    class Solution(object):
        def canCross(self, stones):
            map = {v: i for i, v in enumerate(stones)}
            memo = {0:[0]}
    
            for i in range(len(stones)-1):
                if stones[i] not in memo:
                    continue
    
                for k in memo[stones[i]]:
                    for x in k-1,k,k+1:
                        val = stones[i] + x
    
                        if x <= 0 or val not in map:
                            continue
    
                        if not val in memo:
                            memo[val] = set()
                        memo[val].add(x)
    
            return stones[-1] in memo
    

    so for example: [0,1,3,5,6,8,12,17]
    the memo map looks like this:
    0_1474347629802_Screen Shot 2016-09-20 at 07.00.14.png


Log in to reply
 

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