视频游戏“辐射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 旋转拼出。
思路
贪心
每次找最近的,方法是错误的…
动态规划
感觉是,但是写不出来。
看了官方题解的状态转移方程,感觉也不是很难(还是自己太菜了😭)
转移方程,key
中的第i
个字符与ring
中的第j
个字符最少次数为dp[i][j]
得到状态转移方程
其实仔细想想,这个问题的划分好像也不难,子问题比原问题问题规模小1
,子问题通过枚举计算。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { public: int findRotateSteps(string ring, string key) { vector<vector<int>> pos(26); int l1 = ring.size(), l2 = key.size(); for(int i = 0;i < l1;++i) { pos[ring[i] - 'a'].push_back(i); } vector<vector<int>> dp(l2, vector<int>(l1,INT_MAX)); for(int i = 0;i < l2;++i) { for(int j: pos[key[i] - 'a']) { int min_val = INT_MAX; if(i == 0) { min_val = min(min(abs(j - i), l1 - abs(j - i)) + 1, min_val); } else { for(int k:pos[key[i - 1] - 'a']) { min_val = min(min(abs(k - j) , l1 - abs(k - j)) + dp[i-1][k] + 1, min_val); } } dp[i][j] = min_val; } } int res = INT_MAX; for(auto i:pos[key.back() - 'a']) { res = min(dp.back()[i], res); } return res; } };
|