DP solution in Python using HashMaps and Sets

  • 0

    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:
                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:
                        if not val in memo:
                            memo[val] = set()
            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.