企业官网建设流程全解析

72. 编辑距离 - 力扣（LeetCode）

动态规划：

class Solution { public int minDistance(String word1, String word2) { //子问题:word1的前i个字符转换为word2的前j个字符的最少操作数 //看最后一字符相不相等，相等就是dp[i-1][j-1] //不相等就是插入，删除，替换三种情况取最小值 + 1 //状态转移方程:dp[i][j] = word1[i-1]==word2[j-1] ? //dp[i-1][j-1]:Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1 int m = word1.length(); int 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(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1; } } } return dp[m][n]; } }

时间复杂度：O(MN)

空间复杂度：O(MN)