3579. 字符串转换需要的最小操作数

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • 划分DP
  • 回文串
  • 中心扩展
  • 贪心
  • 哈希表

思路

对字符串的考察极其深刻的好题！

主体是划分DP，因为题目已经提示了让你划分为若干个子串进行转换，

那么显然就有转移方程f[i] = min(f[i], f[j - 1] + cost(j, i))

本题的难点就在于如何求出一个子区间的转换开销呢？

首先发现正序和反序的处理操作应当是一致的，仅仅是需要对比的字母不同而已：

正序是s[i]对比t[i]，例如s[1]的A对上t[1]的D，

反序就是s[i]对上t[L + R - i]，例如s[3]的C对上t[1 + 3 - 3]的D

1
2
3
1 2 3     1 2 3
A B C --> C B A
D E F     D E F

对于单个字符，是交换还是替换，可以发现如下规律：

每个位置只有两种选择，要么交换成对应字母，要么替换成对应字母，不可能变成别的字母

因为哪怕变成别的字母+交换，使得两个字母到了正确位置，花了两次操作机会

而本身每个字母就可以直接变成对应字母，也是两次操作机会

就最终答案而言，变成其他字母一定是不优的，且更麻烦

那么对于每个字母，你只有两种选择，要么原地替换，要么先留着等待后续交换；最后再查看有多少人的需求没被满足，就让它们原地替换即可

所以使用一个哈希表cnt[x][y]记录当前字母x需要转换为y的需求数，

如果后续恰好发现有一个y需要转换为x，即if(cnt[y][x])

那么说明两个人就可以交换，令cnt[x][y]--即可

最后再求和这个26 * 26的哈希表，那就是需要原地替换的次数

得到如下AC代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
 public:
  int minOperations(string word1, string word2) {
    int n = word1.size();
    word1 = "0" + word1, word2 = "0" + word2;
    // cost[l][r]打表, 区间[l, r]的最小开销
    int cost[105][105];
    // cnt[x][y]：字母x需要找一个字母y进行交换
    int cnt[26][26];

    auto calc = [&](int i, int j, bool flag) -> int {
      int ans = 0;
      memset(cnt, 0, sizeof(cnt));
      // 先处理交换的情况
      for (int k = i; k <= j; ++k) {
        int x = word1[k] - 'a';
        int y = flag ? word2[i + j - k] - 'a' : word2[k] - 'a';
        if (x == y) continue;
        if (cnt[y][x])
          cnt[y][x]--, ans += 1;
        else
          cnt[x][y]++;
      }

      // 最后处理直接转换, 如果还有cnt[x][y]剩，说明x对y还有需求
      for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < 26; ++j) {
          if (cnt[i][j]) ans += cnt[i][j];
        }
      }
      return ans;
    };

    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        cost[i][j] = min(calc(i, j, 0), calc(i, j, 1) + 1);
      }
    }

    // DP
    int f[105];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j >= 1; --j) {
        f[i] = min(f[i], f[j - 1] + cost[j][i]);
      }
    }
    return f[n];
  }
};

尽管可以过，但是可以使用字符串的性质来进行优化到平方的复杂度

首先可以发现，DP是每次固定右端点，向左枚举左端点而遍历区间，而正序对比可以放一起做，道理很简单：

1
2
3
2 3 4							    1 2 3 4
A B C  --> 在前面新增一对需要对比的字母, x A B C
D E F							    y D E F

可以发现，区间[2, 4]的转换已经结束了，完全可以使用它们的数据来更新[1, 4]

而反序对比不可以，道理也很显然：

1
2
3
2 3 4							    1 2 3 4
C B A  --> 在前面新增一对需要对比的字母, C B A x
D E F							    y D E F

可以发现，我们之前计算的CBA配对DEF的数据压根用不上，因为现在是CBAx配对yDEF，每个配对都压根不一样

对于反向，我们应考虑回文串，即中心扩展：

1
2
3
2 3 4							    	 1 2 3 4 5
C B A  --> 在前、后分别新增一对需要对比的字母, p C B A x
D E F							         y D E F q

可以很神奇地发现，一旦凑成回文串，那么中间的[2, 4]区间的数据就能用上

最终得到代码如下，需要说明的是，其中的tot可以直接替换掉之前遍历26 * 26哈希表的操作

因为每个错配至少需要1次操作，不管是交换还是原地替换

所以直接tot++，倘若可以交换就不自增，相当于减了一次操作

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
 public:
  int cnt[26][26];

  int minOperations(string word1, string word2) {
    int n = word1.size();
    word1 = "0" + word1, word2 = "0" + word2;

    int rev[105][105];

    for (int i = 1; i <= n; ++i) {
      // 奇数中心
      memset(cnt, 0, sizeof(cnt));
      int tot = 1;
      int l = i, r = i;
      while (l >= 1 && r <= n) {
        int x = word1[l] - 'a', y = word2[r] - 'a';
        if (x != y) {
          if (cnt[y][x])
            cnt[y][x]--;
          else
            cnt[x][y]++, tot++;
        }
        if (l != r) {  // ★ 只有长度>1时才处理第二对
          x = word1[r] - 'a', y = word2[l] - 'a';
          if (x != y) {
            if (cnt[y][x])
              cnt[y][x]--;
            else
              cnt[x][y]++, tot++;
          }
        }
        rev[l][r] = tot;
        --l, ++r;
      }

      // 偶数中心
      if (i < n) {
        memset(cnt, 0, sizeof(cnt));
        tot = 1;
        l = i, r = i + 1;
        while (l >= 1 && r <= n) {
          int x = word1[l] - 'a', y = word2[r] - 'a';
          if (x != y) {
            if (cnt[y][x])
              cnt[y][x]--;
            else
              cnt[x][y]++, tot++;
          }
          x = word1[r] - 'a', y = word2[l] - 'a';
          if (x != y) {
            if (cnt[y][x])
              cnt[y][x]--;
            else
              cnt[x][y]++, tot++;
          }
          rev[l][r] = tot;
          --l, ++r;
        }
      }
    }

    // DP 正向
    int f[105];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      memset(cnt, 0, sizeof(cnt));
      int tot = 0;
      for (int j = i; j >= 1; --j) {
        int x = word1[j] - 'a', y = word2[j] - 'a';
        if (x != y) {
          if (cnt[y][x])
            cnt[y][x]--;
          else
            cnt[x][y]++, tot++;
        }
        f[i] = min(f[i], f[j - 1] + min(rev[j][i], tot));
      }
    }
    return f[n];
  }
};