Very concise solution. The only thing I don't understand is why you iterate from m-1 to 0, not from 0 to m-1. Iterate from 0 to m-1won't give correct solution. Could you please explain? Thanks.

@caofang I think this is a top-down approach. Assume we have already solved the first K-1 characters, then for the last character, we only need to find the closest matched character from clockwise direction and anti-clockwise direction.

The same idea. But I use hashmap for the state of every step, which make it clear.

def findRotateSteps(self, ring, key):
# the distance between two points (i, j) on the ring
def dist(i, j):
return min(abs(i - j), len(ring) - abs(i - j))
# build the position list for each character in ring
pos = {}
for i, c in enumerate(ring):
if c in pos:
pos[c].append(i)
else:
pos[c] = [i]
# the current possible state: {position of the ring: the cost}
state = {0: 0}
for c in key:
next_state = {}
for j in pos[c]: # every possible target position
next_state[j] = float('inf')
for i in state: # every possible start position
next_state[j] = min(next_state[j], dist(i, j) + state[i])
state = next_state
return min(state.values()) + len(key)

@davidxie Because the length of the ring won't exceed 100. Shift left 8 bits means offset * 256, then use it plus cur to build up unique integer k which is used as key of the hash map.