514. Freedom Trail
手寫了TLE版本固灵，加了一些memory捅伤，不過還是TLE∥撞＃基本思路是對(duì)的丛忆，只是有一點(diǎn)問題，不用找到所有的值仍秤，只需要針對(duì)某一個(gè)index熄诡，找到之前的第一個(gè)和之后的第一個(gè)就可以了。
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]
