给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

解题思路

参考：编辑距离

• 定义状态：dp[i][j] 为将 word1 的前 i 个字母转换为 word2 的前 j 个字母所需要的最少操作数
  • i 控制 word1（上下）
  • j 控制 word2（左右）
• 基础情况：考虑 word1 或 word2 为空串情况
  • 首行：word1 是空串时，要把 word2 插入
  • 首列：word2 是空串时，要把 word1 全部删除
• 状态转移：
  • 如果末尾字符相同，则 word1、word2 规模都变小：dp[i][j] --> dp[i-1][j-1]
  • 如果末尾字符不同，有三种情况，取三种情况的最小值再加一：dp[i][j] = min(插入,删除,替换) + 1
    1. 插入：word1 尾部插入字符，使得 word1 末尾和 word2 末尾相同，word2 规模变小
    • dp[i][j] --> dp[i][j-1]
    2. 删除：word1 尾部删除字符，word1 规模变小
    • dp[i][j] --> dp[i-1][j]
    3. 替换：word1 尾部替换字符，使得 word1 末尾和 word2 末尾相同，word1、word2 规模都变小
    • dp[i][j] --> dp[i-1][j-1]

Java 实现

	public int minDistance(String word1, String word2) {
		int m = word1.length();
		int n = word2.length();
		int dp[][] = new int[m+1][n+1];
		// 初始化首列，即 word2 是空串时，要把 word1 全部删除
		for (int i = 0; i <= m; i++){
			dp[i][0] = i;
		}
		// 初始化首行，即 word1 是空串时，要按照 word2 全部插入到 word1 中
		for (int i = 0; i <= n; i++){
			dp[0][i] = i;
		}
		// 三种情况：
		// 1. 插入： dp[i][j] --> dp[i][j-1]
		// 2. 删除： dp[i][j] --> dp[i-1][j]
		// 3. 替换： dp[i][j] --> dp[i-1][j-1]
		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][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
				}
			}
		}
		return dp[m][n];
	}