【Leetcode 热题 100】72. 编辑距离

问题背景

给你两个单词 $wor{d}_1$ 和 $wor{d}_2$， 请返回将 $wor{d}_1$ 转换成 $wor{d}_2$ 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

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

数据约束

• $0\le wor{d}_1.length,wor{d}_2.length\le 500$
• $wor{d}_1$ 和 $wor{d}_2$ 由小写英文字母组成

解题过程

和 昨天的题 实现思路上非常相似，要想清楚的是，如果盯着其中一个字符串来修改，那么所有的操作都可以转化为删除。
在一个字符串上添加，和在另一个字符串上删除，这两种方案在效果和操作次数上是等效的；在一个字符串中替换，和在两个字符串中同时删除，这两种方案，在效果和操作次数上是等价的。

具体实现

递归

class Solution {private char[] chW1, chW2;private int[][] memo;public int minDistance(String word1, String word2) {chW1 = word1.toCharArray();chW2 = word2.toCharArray();int m = chW1.length;int n = chW2.length;memo = new int[m][n];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(m - 1, n - 1);}private int dfs(int i, int j) {if (i < 0) {return j + 1;}if (j < 0) {return i + 1;}if (memo[i][j] != -1) {return memo[i][j];}if (chW1[i] == chW2[j]) {return memo[i][j] = dfs(i - 1, j - 1);}return memo[i][j] = Math.min(Math.min(dfs(i - 1, j), dfs(i, j - 1)), dfs(i - 1, j - 1)) + 1;}
}

递推

class Solution {public int minDistance(String word1, String word2) {char[] chW1 = word1.toCharArray();char[] chW2 = word2.toCharArray();int m = chW1.length;int n = chW2.length;int[][] dp = new int[m + 1][n + 1];for (int j = 1; j <= n; j++) {dp[0][j] = j;}for (int i = 0; i < m; i++) {dp[i + 1][0] = i + 1;for (int j = 0; j < n; j++) {dp[i + 1][j + 1] = chW1[i] == chW2[j] ? dp[i][j] : Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;}}return dp[m][n];}
}