8.23 - hard - 98

514. Freedom Trail

手写了TLE版本，加了一些memory，不过还是TLE。基本思路是对的，只是有一点问题，不用找到所有的值，只需要针对某一个index，找到之前的第一个和之后的第一个就可以了。

class Solution(object):
    def findRotateSteps(self, ring, key):
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
        ring = list(ring)
        return self.search(ring, key, 0, {}) + len(key)
        
    
    def search(self, ring, key, pos, m):
        if pos == len(key):
            return 0
        if str(ring)+str(pos) in m:
            return m[str(ring)+str(pos)]
        res = sys.maxint
        for i in range(len(ring)):
            if ring[i] == key[pos]:
                new_ring = ring[i:] + ring[:i]
                res = min(res, self.search(new_ring, key, pos + 1, m)+min(i, len(ring)-i))
        m[str(ring)+str(pos)] = res
        return res

class Solution(object):
    def findRotateSteps(self, ring, key):
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
        if not ring or not key:
            return 0
        mem = [[0 for _ in range(len(key))] for _ in range(len(ring))]
        return self.findShortest(ring, 0, key, 0, mem)
    
    def findShortest(self, arr, p, key, pos, mem):
        if pos == len(key):
            return 0
        if mem[p][pos] > 0:
            return mem[p][pos]
        c1 = c2 = 0
        i = j = p
        # from pericular position of p, find 
        while arr[i] != key[pos]:
            i = (i+1) % len(arr)
            c1 += 1
            
        while arr[j] != key[pos]:
            j= (j-1+len(arr)) % len(arr)
            c2 += 1
        r1 = self.findShortest(arr, i, key, pos+1, mem) + c1 + 1
        r2 = self.findShortest(arr, j, key, pos+1, mem) + c2 + 1
        mem[p][pos] = min(r1,r2)
        return mem[p][pos]