电子游戏“辐射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。
C++代码如下:
class Solution {
public:
int findRotateSteps(string ring, string key) {
vector<int> m[26];
int n1 = ring.size();
int n2 = key.size();
for (int i = 0; i < n1; i++) {
m[ring[i] - 'a'].push_back(i);
}
vector<vector<int>> dp(key.size(), vector<int>(ring.size(), INT_MAX));
for (int j: m[key[0] - 'a']) {
dp[0][j] = min(j, n1 - j) + 1;
}
for (int i = 1; i < n2; i++) {
int pos = key[i] - 'a';
for (int j : m[pos]) {
for (int k = 0; k < n1; k++) {
if (dp[i - 1][k] != INT_MAX) {
int a = min(j, k);
int b = max(j, k);
dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(b - a, n1 + a - b) + 1);
}
}
}
}
int result = INT_MAX;
for (int i: m[key[n2 - 1] - 'a']) {
result = min(result, dp[n2 - 1][i]);
}
return result;
}
};