• 困难
  • 中等
  • 简单

    题目描述

    电子游戏“辐射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 每日一题 514. 自由之路

例如：
514. 自由之路 - 图1 

  1. 输入: ring = "godding", key = "gd"
  2. 输出: 4
  3. 解释:
  4.  对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
  5.  对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
  6.  当然, 我们还需要1步进行拼写。
  7.  因此最终的输出是 4。

解题思路

  1. 很容易想到的解决思路是：记录一个当前位置，然后遍历每一个可以key中的下一个字符相匹配的地方，当key中字符都匹配完成之后，选取一个最小的数值作为答案。此方法的复杂度为514. 自由之路 - 图2，复杂度太高，无法通过。
  2. 需要对上面的过程进行优化
    1. 将所有单词的出现的位置都记录下来，然后每次可以根据下一个字符是什么直接找到它的位置
    2. 记忆化：计算由上一个字符到达当前字符所在位置的最小值，然后保存下来

      代码

      1. class Solution {
      2. public:
      3. int findRotateSteps(string ring, string key) {
      4.   map<char, vector<int>> char_indexs;
      5.   vector<int> last_pos(1, 0);
      6.   vector<int> last_val(1, 0);
      7.   for (int i = 0; i < ring.length(); i++) {
      8.       char_indexs[ring[i]].push_back(i);
      9.   }
      10.   int result = INT_MAX;
      11.   int length = ring.length();
      12.   int length2 = key.length();
      13.   dfs(result, char_indexs, key, 0, last_pos, length, length2, last_val);
      14.   return result + key.length();
      15. }
      16. void dfs(int& result, map<char, vector<int>>& char_indexs, string& key, int curr_char, vector<int> last_pos, int& length, int& length2, vector<int> last_value){
      17.   if (curr_char == length2) {
      18.       for (auto& item: last_value) {
      19.           result = min(result, item);
      20.       }
      21.       return;
      22.   }
      23.   vector<int> temp;
      24.   vector<int> temp_val;
      25.   for (auto& item:char_indexs[key[curr_char]]) {
      26.       // 遍历当前字符的所在位置
      27.       // 记录上一个字符到达当前字符的最短路径
      28.       int mins = INT_MAX;
      29.       // 对上一个字符的位置进行遍历
      30.       for (int i = 0; i < last_pos.size(); i++) {
      31.           int c_pos = last_pos[i];
      32.           int value = last_value[i];
      33.           int t = abs(item-c_pos);
      34.           t = min(length-t, t);
      35.           mins = min(t + value, mins);
      36.       }
      37.       temp_val.push_back(mins);
      38.       temp.push_back(item);
      39.   }
      40.   dfs(result, char_indexs, key, curr_char + 1, temp, length, length2, temp_val);
      41. }
      42. };