DeepSeek LeetCode 3579. 字符串转换需要的最小操作数 Java实现

解题思路

采用区间DP + 贪心匹配：

· 核心操作：可以将 word1 分割成若干连续子串，对每个子串可执行替换、交换、反转三种操作。
· 贪心匹配：处理一个子串时，遇到不匹配的字符对 (a, b)，优先寻找之前是否出现过相反的不匹配对 (b, a)。如果找到，说明这两个位置可以一次交换同时修复；否则记录当前不匹配对，等待后续配对。
· DP定义：dp[i] 表示将 word1[0..i-1] 转换为 word2[0..i-1] 的最小操作数。
· 状态转移：枚举最后一个子串的起点 j，取不反转和先反转两种情况的最小值：
· dp[i] = min(dp[i], dp[j] + cost(j, i, false))
· dp[i] = min(dp[i], dp[j] + 1 + cost(j, i, true))

---

Java 实现

```java
class Solution {
public int minOperations(String word1, String word2) {
int n = word1.length();
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0;

for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
// 情况1：不反转子串 word1[j..i-1]
int cost1 = calcCost(word1, word2, j, i, false);
dp[i] = Math.min(dp[i], dp[j] + cost1);

// 情况2：先反转子串 word1[j..i-1]，再处理（反转本身消耗1次操作）
int cost2 = calcCost(word1, word2, j, i, true);
dp[i] = Math.min(dp[i], dp[j] + 1 + cost2);
}
}
return dp[n];
}

/**
* 计算将 word1[l..r-1] 转换为 word2[l..r-1] 所需的最少操作数（只使用替换和交换）。
* @param reversed true 表示先将 word1 的这段子串反转，再与 word2 对应位置比较
*/
private int calcCost(String word1, String word2, int l, int r, boolean reversed) {
int[][] pending = new int[26][26]; // pending[a][b] 表示等待匹配的 (a, b) 数量
int swaps = 0; // 交换操作次数 = 不匹配对数量

for (int k = 0; k < r - l; k++) {
int idx1 = reversed ? r - 1 - k : l + k;
int idx2 = l + k;
int a = word1.charAt(idx1) - 'a';
int b = word2.charAt(idx2) - 'a';

if (a == b) continue;

// 检查是否有相反的 (b, a) 等待配对
if (pending[b][a] > 0) {
pending[b][a]--; // 配对成功，抵消一次交换
} else {
pending[a][b]++;
swaps++; // 新增一个待匹配的不匹配对
}
}
return swaps; // 每个不匹配对需要一次交换或替换操作
}
}
```

---

复杂度分析

· 时间复杂度：O(n³)，其中 n ≤ 100。外层枚举 i 和 j 共 O(n²) 种子串，calcCost 遍历子串长度 O(n)，总计 O(n³)。
· 空间复杂度：O(n + 26²)，dp 数组 O(n)，计数数组 O(26²) 为常数。