LeetCode72.编辑距离（多维动态规划）

题目LeetCode 72给你两个单词word1和word2请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作插入一个字符删除一个字符替换一个字符示例示例 1输入word1 horse, word2 ros输出3解释horse - rorse (将 h 替换为 r)rorse - rose (删除 r)rose - ros (删除 e)Python解法代码示例class Solution: def minDistance(self, word1: str, word2: str) - int: n, m len(word1), len(word2) dp [[0] * (m 1) for _ in range(n 1)] for i in range(n 1): dp[i][0] i for j in range(m 1): dp[0][j] j for i in range(1,n 1): for j in range(1,m 1): delete_dp dp[i - 1][j] 1 insert_dp dp[i][j - 1] 1 replace_dp dp[i - 1][j - 1] if word1[i - 1] ! word2[j - 1]: replace_dp 1 dp[i][j] min(delete_dp, insert_dp, replace_dp) return dp[n][m]解释1边界初始化for i in range(n 1): dp[i][0] iword2为空串只能把word1逐个删除有几个字符就删几次。for j in range(m 1): dp[0][j] jword1为空串只能逐个插入word2字符有几个字符就插几次。2状态转换1删除操作delete_op dp[i - 1][j] 1word1删掉第i个字符问题缩小为word1前i-1个匹配word2前j个操作 1。2插入操作insert_op dp[i][j - 1] 1word1插入一个字符匹配word2[j-1]问题缩小为word1前i个匹配word2前j-1个操作 1。3替换操作replace_op dp[i - 1][j - 1] if word1[i - 1] ! word2[j - 1]: replace_op 1如果word1[i-1] word2[j-1]字符相等不用操作直接继承dp[i-1][j-1]如果不相等替换一次操作数 14取最小值dp[i][j] min(delete_op, insert_op, replace_op)三种操作选步数最少的。过程简单演示以word1 howord2 ro为例Java解法代码示例class Solution { public int minDistance(String word1, String word2) { int n word1.length(); int m word2.length(); // dp[i][j]word1前i个字符 → word2前j个字符 的最小编辑距离 int[][] dp new int[n 1][m 1]; // 边界初始化word2 为空只能删除 word1 for (int i 0; i n; i) { dp[i][0] i; } // 边界初始化word1 为空只能插入 word2 for (int j 0; j m; j) { dp[0][j] j; } // 动态规划填表 for (int i 1; i n; i) { for (int j 1; j m; j) { // 删除操作删掉 word1 第 i 个字符 int delete dp[i - 1][j] 1; // 插入操作给 word1 插入一个字符匹配 word2 第 j 个 int insert dp[i][j - 1] 1; // 替换 / 不操作看末尾字符是否相等 int replace dp[i - 1][j - 1]; if (word1.charAt(i - 1) ! word2.charAt(j - 1)) { replace; } // 三种操作取最小 dp[i][j] Math.min(Math.min(delete, insert), replace); } } return dp[n][m]; } }C解法代码示例class Solution { public: int minDistance(string word1, string word2) { int n word1.size(); int m word2.size(); // dp[i][j]word1前i个字符 转为 word2前j个字符 的最小编辑距离 vectorvectorint dp(n 1, vectorint(m 1, 0)); // 边界1word2为空只能不断删除word1 for (int i 0; i n; i) { dp[i][0] i; } // 边界2word1为空只能不断插入word2 for (int j 0; j m; j) { dp[0][j] j; } // 遍历填充DP表 for (int i 1; i n; i) { for (int j 1; j m; j) { // 1. 删除操作 int del dp[i - 1][j] 1; // 2. 插入操作 int ins dp[i][j - 1] 1; // 3. 替换 / 无需操作 int rep dp[i - 1][j - 1]; // 当前字符不同需要替换操作数1 if (word1[i - 1] ! word2[j - 1]) { rep 1; } // 取三种操作最小值 dp[i][j] min({del, ins, rep}); } } return dp[n][m]; } };