自由之路
视频游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。
给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
旋转 ring 拼出 key 字符 key[i] 的阶段中：
您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。 如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/freedom-trail 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入: ring = "godding", key = "gd"
输出: 4
解释:
对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。
提示：
ring 和 key 的字符串长度取值范围均为 1 至 100；
两个字符串中都只有小写字符，并且均可能存在重复字符；
字符串 key 一定可以由字符串 ring 旋转拼出。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/freedom-trail
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案
对于该问题的第一思路为按题意模拟，对于key的每个字符有两种选择顺/逆时针旋转，递归枚举出所有可能性，总体时间复杂度为O（N * 2 ^ N ）。N范围在100，明显该方案过不了。
定义dp[i] [j] 为逐个拼完key[0:i]元素，最终ring[j]指向12:00方向的最少步数。
首先只有key[i] == ring[j]时才有意义，否则拼不出来
然后我们需要寻找dp[i] [j]的上一个状态（即其可以由那些状态转移而来），发现其可以由dp[i - 1] [k]（此时只需key[i] == ring[k]即可）。
上式中abs(j - k)描述的是由dp[i - 1] [k]转移到dp[i] [j] 使用的是逆时针旋转， N - abs(j - k)则描述的是由dp[i - 1] [k]转移到dp[i] [j] 使用的是顺时针旋转。
代码如下：
func findRotateSteps(ring string, key string) int {
N := len(ring)
M := len(key)
dp := make([][]int, 0, M)
reme := make([][]int,26, 26)
ans := 0x3f3f3f
for i := 0; i < M; i++{
dp = append(dp, make([]int, N, N))
}
for i := 0; i < M; i++{
for j := 0; j < N; j++{
dp[i][j] = 0x3f3f3f
}
}
for idx, val := range ring{
reme[val - 'a'] = append(reme[val - 'a'], idx)
if ring[idx] == key[0] {
dp[0][idx] = min(idx, N - idx) + 1
}
}
for i := 1; i < M; i++{
for j := 0; j < N; j++{
if key[i] != ring[j]{
continue
}
for _, k := range reme[key[i - 1] - 'a']{
dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(j - k), N - abs(j - k)) + 1)
}
if i == M - 1{
ans = min(ans, dp[i][j])
}
}
}
return ans
}
func min(num1, num2 int) int{
if num1 < num2{
return num1
}else{
return num2
}
}
func abs(num1 int) int{
if num1 < 0{
return -1 * num1
}else{
return num1
}
}时间复杂度为O（N ^ 3）
腾讯云开发者
