每日一题 72编辑距离（LCS）（灵神笔记）

本文主要是介绍每日一题 72编辑距离（LCS）（灵神笔记），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

编辑距离
你两个单词 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 <= 500
word1 和 word2 由小写英文字母组成

题解

记忆化搜索

class Solution {private char[] s, t;private int[][] cache;public int minDistance(String word1, String word2) {s = word1.toCharArray();t = word2.toCharArray();int n = s.length, m = t.length;cache = new int[n][m];for (int i = 0; i < n; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1, m - 1);}public int dfs(int i, int j) {//与LCS相同，dfs(i,j-1)相当于插入，dfs(i-1,j)相当于删除，dfs(i-1,j-1)相当于替换if (i < 0) {return j + 1;}if (j < 0) {return i + 1;}if (cache[i][j] != -1) {return cache[i][j];}if (s[i] == t[j]) {return cache[i][j] = dfs(i - 1, j - 1);}return cache[i][j] = Math.min(Math.min(dfs(i,j-1),dfs(i-1,j)),dfs(i-1,j-1))+1;}
}

递推

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

空间优化

class Solution {public int minDistance(String word1, String word2) {char[] t = word2.toCharArray();int m = t.length;int[] f = new int[m + 1];for (int j = 1; j <= m; j++) {f[j] = j;}for (char x : word1.toCharArray()) {int pre = f[0];f[0]++;for (int j = 0; j < m; j++) {int tmp = f[j + 1];f[j + 1] = x == t[j] ? pre : Math.min(Math.min(f[j + 1],f[j]),pre) + 1;pre = tmp;}}return f[m];}
}