JAVA练习358- 编辑距离

题目概览给你两个单词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)提示0 word1.length, word2.length 500word1和word2由小写英文字母组成来源72. 编辑距离 - 力扣LeetCode解题分析方法动态规划用 i 表示在 word1 遍历的位置j 表示在 word2 遍历的位置用二维数组 dp 存储结果那么当 word1 [ i ] word2 [ j ] 时说明不用操作那么就看 i - 1 和 j - 1 的操作数 1即 dp[ i ][ j ] dp[ i-1 ][ j-1 ] 1当 word1 [ i ] ! word2 [ j ] 时需要比较三个操作的步骤替换就是看 dp[ i - 1 ][ j - 1] 的操作数然后当前两个字母替换即 dp[ i - 1 ][ j - 1 ] 1插入删除就是看 dp[ i - 1][ j ] 和 dp[ i ][ j - 1] 的操作数 1那么最小操作步骤就是取三个的最小值即dp[ i ][ j ] min {dp[ i - 1 ][ j - 1 ], dp[ i-1 ][ j ], dp[ i ][ j-1 ]} 1由于 i 0 或 j 0 时无法获取 i - 1 或 j - 1 的值因此我们可以将二维数组加一位i 0 或 j 0 时填充空字符串和对应的字符串的比较结果后续从 i 1 和 j 1 开始遍历。时间复杂度O(mn)空间复杂度O(mn)class Solution { public int minDistance(String word1, String word2) { int m word1.length(), n word2.length(); int[][] dp new int[m1][n1]; for (int i 1; i m; i) { dp[i][0] dp[i-1][0] 1; } for (int j 1; j n; j) { dp[0][j] dp[0][j-1] 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(dp[i-1][j], dp[i][j-1]) 1; dp[i][j] Math.min(dp[i][j], dp[i-1][j-1] 1); } } } return dp[m][n]; } }