72.编辑距离

题目描述

给定两个单词 word1 和 word2，计算将 word1 转换为 word2 所需的最少操作数。允许的操作：插入、删除、替换。

示例 1

输入: word1 = "horse", word2 = "ros"
输出: 3

示例 2

输入: word1 = "intention", word2 = "execution"
输出: 5

解题思路：二维动态规划（Levenshtein 距离）

设 dp[i][j] 为将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最少操作数。

转移：

• 若 word1[i-1] == word2[j-1]，dp[i][j] = dp[i-1][j-1]。
• 否则，dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)，分别对应删除、插入、替换。

边界：dp[i][0] = i，dp[0][j] = j。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String word1 = scanner.next();
        String word2 = scanner.next();

        Solution solution = new Solution();
        int result = solution.minDistance(word1, word2);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) { dp[i][0] = i; }
        for (int j = 0; j <= n; j++) { dp[0][j] = j; }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

空间优化：一维滚动

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String word1 = scanner.next();
        String word2 = scanner.next();

        Solution solution = new Solution();
        int result = solution.minDistance(word1, word2);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) { dp[j] = j; }
        for (int i = 1; i <= m; i++) {
            int prev = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev;
                } else {
                    dp[j] = Math.min(Math.min(dp[j] + 1, dp[j - 1] + 1), prev + 1);
                }
                prev = tmp;
            }
        }
        return dp[n];
    }
}

复杂度分析

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)（二维），优化为 O(n)（一维滚动）。

三种操作对应三条转移路径，边界为空串对齐，按行列推进即可得到最优编辑序列的最少操作数。