LeetCode 514. Freedom Trail – Ysing's blog

LeetCode 514. Freedom Trail – Ysing's blog

由于做出来的时候posted在discuss了，所以我直接复制里面的内容

• 看Tag上dp上打了个冒号，这似乎不完全算是一个dp solution
• 基本思路：

1. 对于解一个key，我们可以将这个key的长度作为我们接这道题的step,每一步step接一个char,解到最后一个字符最小step就是我们需要求的答案
2. 所以算法开始，我们需要知道，key对应的每一个char在string ring中的哪一个位置，需要对ring for一遍，将对应的char记录在相应的mp中，这样可以节省很多的搜索时间。
3. 开始搜索key的循环，算法第一步开始的index为 ring[0],需要求转动ring，使达到ring[index]==key[0](第一步)的步数最小，因为可能ring中不止有一个key[0]，所以需要对每一个符合的进行选择，（每一个dp[i][j],记录的实际就是在第i步时，通过起点到达j的最短step,主要是考虑rotate left or right）
4. 依次循环key.size()步后结束循环
5. 对最后一个dp数组for出最小的值,return minStep + key.size()即是最小的步数

Simple dp idea

1. recording each index of characters in ring,beacuse each characters we have search in this time would be starting index in the next search
2. How could we solve the problem that rotate the ring to the left or right ? My idea is min((tmp[j] + size -it)%size,(it + size - tmp[j])%size)

• Suppose you want to rotate the ring to the right and search 'k', and the size is 5. We could calculate it by this + size -k(index)%size

this -  -  -  -  k 

• If we want to rotate the ring to the left，what should we do? It is the same problem with above problem,move this to it 's right,and reach k

k -  -  -  -   this 

• So we could calculate it by k(index) + size -this%size
• There are many people use abs() instead of %size,I think it's faster than mine :)

Read full article from LeetCode 514. Freedom Trail – Ysing's blog