【Leetcode】1320. Minimum Distance to Type a Word Using Two Fingers

题目地址：

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/description/

给定一个键盘如下：
再给定一个只含英文大写字母的长$n$字符串$s$，允许用两个手指打字，手指移动的代价是两个位置的曼哈顿距离。问打完$s$需要的总代价最少是多少。任意一个手指打的第一个字符不需要代价。

思路是动态规划。设$f[k][x][y]$为已经打完$k$个字符，第一个手指在$x$，另一个手指在$y$的情况下所需要的最小代价。那么初始条件为$f[0][.][.]=0$，转移的时候只需要枚举下一个字符是从第一个手指转移过去的还是第二个手指转移过去的即可。所以$f[k+1][z][y]$可以由$f[k][x][y]+(x\to z)$来更新，以此类推。最后返回$\min f[n][.][.]$即可。代码如下：

class Solution {
 public:
  int minimumDistance(string s) {
    int n = s.size();
    auto dist = [&](int x, int y) {
      return abs(x / 6 - y / 6) + abs(x % 6 - y % 6);
    };

    int f[n + 1][26][26];
    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < 26; i++)
      for (int j = 0; j < 26; j++) f[0][i][j] = 0;

    for (int i = 0; i < n; i++) {
      int pos = s[i] - 'A';
      for (int x = 0; x < 26; x++)
        for (int y = 0; y < 26; y++) {
          f[i + 1][pos][y] = min(f[i + 1][pos][y], f[i][x][y] + dist(x, pos));
          f[i + 1][x][pos] = min(f[i + 1][x][pos], f[i][x][y] + dist(y, pos));
        }
    }

    int res = 0x3f3f3f3f;
    for (int i = 0; i < 26; i++)
      for (int j = 0; j < 26; j++) res = min(res, f[n][i][j]);
    return res;
  }
};
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

时空复杂度$O(n)$。