题目描述
电子游戏“辐射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
的下一个字符(下一阶段), 直至完成所有拼写。
样例
输入: ring = "godding", key = "gd"
输出: 4
解释:
对于 key 的第一个字符 'g',已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 'd',我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。
提示:
ring
和key
的字符串长度取值范围均为1
至100
;- 两个字符串中都只有小写字符,并且均可能存在重复字符;
- 字符串
key
一定可以由字符串ring
旋转拼出。
算法分析
时间复杂度 $O(n^3)$
Java 代码
class Solution {
public int findRotateSteps(String ring, String key) {
int n = ring.length(), m = key.length();
ring = " " + ring;
key = " " + key;
int[][] f = new int[m + 10][n + 10];
for(int i = 0;i <= m;i ++) Arrays.fill(f[i], 0x3f3f3f3f);
f[0][1] = 0;
for(int i = 1;i <= m;i ++)
for(int j = 1;j <= n;j ++)
if(key.charAt(i) == ring.charAt(j))
{
for(int k = 1;k <= n;k ++)
{
int t = Math.abs(j - k);
f[i][j] = Math.min(f[i][j], f[i - 1][k] + Math.min(n - t, t) + 1);
}
}
int res = 0x3f3f3f3f;
for(int i = 1;i <= n;i ++) res = Math.min(res, f[m][i]);
return res;
}
}