解题思路

采用区间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²) 为常数。