fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
经典动态规划：编辑距离 :: labuladong的算法小抄
递归Java版（带备忘录）
class Solution {
int[][] memo;
public int minDistance(String word1, String word2) {
memo = new int[word1.length()][word2.length()];
return dp(word1, word2, word1.length()-1, word2.length()-1);
}
private int dp(String s1, String s2, int i, int j){
if(i == -1) return j+1;
if(j == -1) return i+1;
if(memo[i][j] != 0) return memo[i][j];
if(s1.charAt(i) == s2.charAt(j)){
memo[i][j] = dp(s1,s2,i-1,j-1);
}else{
int a = dp(s1,s2,i,j-1) + 1;
int b = dp(s1,s2,i-1,j) + 1;
int c = dp(s1,s2,i-1,j-1) + 1;
memo[i][j] = Math.min(a, Math.min(b, c));
}
return memo[i][j];
}
}
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
max_distance = max(len(word1),len(word2))
# base case
if len(word1) * len(word2)==0:
return max_distance
#dp table
row = [max_distance for _ in range(len(word2)+1)]
dp = [row.copy() for _ in range(len(word1)+1)]
dp[0][0] = 0
# base case
for i in range(len(word1)+1):
dp[i][0] = i
for j in range(len(word2)+1):
dp[0][j] = j
for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
char_1 = word1[i-1]
char_2 = word2[j-1]
if char_1 == char_2:
# 相同的情况上，就不用操作，就等于上一个阶段
dp[i][j] = dp[i-1][j-1]
else:
# 不相同的情况上，有三种操作的可能 1）删除左边 2） 删除右边 3）替换/ 插入跟删除本质是同一个种操作
dp[i][j] = 1 + min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
return dp[-1][-1]
东哥，第三个大标题上面的大段代码，关于dp数组的定义，是不是不大对？
// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i-1][j-1]
莫不是应该写成？
// 定义：s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离是 dp[i][j]
class Solution {
public:
int memo[501][501];
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
memo[i][j] = 0;
return dp(m,n, word1, word2);
}
int dp(int i, int j, string word1, string word2){
if(memo[i][j]!=0)
return memo[i][j];
if(i==0) return memo[i][j] = j;
if(j==0) return memo[i][j] =i;
if(word1[i-1]==word2[j-1])
memo[i][j] = dp(i-1,j-1, word1, word2);
else
memo[i][j] = min(min(dp(i-1,j,word1,word2)+1,dp(i,j-1,word1,word2)+1),dp(i-1,j-1,word1,word2)+1);
return memo[i][j];
}
};
#递归+备忘录--python class Solution: def minDistance(self, word1: str, word2: str) -> int:
help_dict={}
def dp(i: int, j: int):
if (i,j) in help_dict:
return help_dict[(i,j)]
#base case: word1没走完，word1全删掉，word2没走完，word1全插入
if i == -1:
return j+1
if j == -1:
return i+1
if word1[i] == word2[j]:
help_dict[(i,j)] = dp(i-1, j-1) #本来就匹配的，i,j前移
else:
help_dict[(i,j)] = min(dp(i, j-1)+1, #插入字符后，匹配了，但i不变，j左移
dp(i-1,j)+1, #删除字符后，i前移，j不变
dp(i-1, j-1)+1)#替换字符后，匹配了，i前移，j也前移
return help_dict[(i,j)]
return dp(len(word1)-1, len(word2)-1)
自底向上C++代码
class Solution {
public:
int minDistance(string word1, string word2) {
int size1 = word1.size(), size2 = word2.size();
vector<vector<int>> dp(size1 + 1, vector<int>(size2 + 1));
//base case
for(int i = 1; i<= size1; ++i)
dp[i][0] = i;
for(int j = 1; j <= size2; ++j)
dp[0][j] = j;
//自底向上求解
for(int i = 1; i <= size1; ++i) {
for(int j = 1; j <= size2; ++j) {
if(word1[i - 1] == word2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = minAbc(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
}
}
return dp[size1][size2];
}
int minAbc(int a, int b, int c) {
return min(a, min(b, c));
}
};
东哥，递归函数中插入的情况，“我直接在s1[i]插入一个和s2[j]一样的字符"，有点不理解； 根据动图，s1中插入新字母加后，s1[i]对应的字母没有变化，是不是这样表述更好“直接在s1[i+1]插入一个...”。
javascript version
// 动态规划-备忘录
var minDistance = function(word1, word2) {
let m = word1.length;
let n = word2.length;
// 备忘录初始化为特殊值 表示还未计算
let memo = new Array(m).fill(-1).map(() => new Array(n).fill(-1));
return dp(word1, m - 1, word2, n - 1);
function dp(s1, i, s2, j) {
if (i == -1) return j + 1;
if (j == -1) return i + 1;
// 查询备忘录 避免重叠子问题 递归树剪枝
if (memo[i][j] != -1) {
return memo[i][j];
}
// 状态转移 结果存入备忘录
if (s1[i] === s2[j]) {
memo[i][j] = dp(s1, i - 1, s2, j - 1);
} else {
memo[i][j] = Math.min(
dp(s1, i, s2, j - 1) + 1,
dp(s1, i - 1, s2, j) + 1,
dp(s1, i - 1, s2, j - 1) + 1
);
}
return memo[i][j];
}
};
// javascript-DP_table
var minDistance = function(word1, word2) {
let m = word1.length;
let n = word2.length;
// 定义s1[0..i]和s2[0..j]的最小编辑距离是dp[i+1][j+1]
let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
// base case
for (let i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (let j = 1; j <= n; j++) {
dp[0][j] = j;
}
// 自底向上求解
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
);
}
}
}
// 储存着整个s1和s2的最小编辑距离
return dp[m][n];
};
在i=-1的时候，返回的为什么是j+1而不是j，因为在递归函数中i与j记录的字符串数组中的下标值，而数组的起始下标是从0开始的，j=-1时候同理
DP Table 压缩空间 O(min(M, N))
空间复杂度是可以压缩成 O(min(M, N)) 的（M，N 是两个字符串的长度）。不难，但是可解释性大大降低，读者可以自己尝试优化一下。
应该是东哥说的 O(min(M,N)) 的空间复杂度了。
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function (word1, word2) {
// 交换，使得 word2 属于最短一方, 这样节约最省空间
if (word1.length < word2.length) {
let t = word2;
word2 = word1;
word1 = t;
}
// 初始化基准情况
let dp = [];
for (let i = 0; i <= word2.length; i++) {
dp[i] = i;
}
// 状态转移
for (let i = 1; i <= word1.length; i++) {
// base case
let dp_i = i - 1;
dp[0] = i;
for (let j = 1; j <= word2.length; j++) {
let t = dp[j];
if (word1[i - 1] === word2[j - 1]) {
// skip
dp[j] = dp_i;
} else {
dp[j] = 1 + Math.min(dp_i, dp[j - 1], dp[j]);
}
dp_i = t;
}
}
return dp[word2.length];
};
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if(len1 + len2 != len3){
return false;
}
//dp[i][j] 表示 s1[0..i-1] s2[0..j-1] 是否能平凑出 s3[0..i+j-1]
boolean[][] dp = new boolean[len1+1][len2+1];
dp[0][0] = true;
for(int i = 1; i<=len1;i++){
//当前 s2 为空字符串的时候， 就需要看s3的字符是否与 s1 中的是否相同了 ， 如果相同， 则可以平凑出来
if(s1.charAt(i-1) == s3.charAt(i-1)){
dp[i][0] = dp[i-1][0] && true ;
}else{
dp[i][0] = false;
}
}
for(int j = 1 ; j<=len2;j++){
if(s2.charAt(j-1) == s3.charAt(j-1)){
dp[0][j] = dp[0][j-1];
}else{
dp[0][j] = false;
}
}
for(int i = 1; i<=len1;i++){
for(int j = 1 ; j<=len2;j++){
//当前s3 位置的可以靠 s1 可以凑出 ， 则当前位置的依靠前面的状态转换过来
if(s1.charAt(i-1) == s3.charAt(i+j-1) ){
dp[i][j] = dp[i-1][j]; //当前位置i可以凑出来的， 那么就要看前面的i-1是否可以凑出来了
}
//同理
if(s2.charAt(j-1) == s3.charAt(i+j-1)){
dp[i][j] = dp[i][j] || dp[i][j-1];
}
}
}
return dp[len1][len2];
}
}
通过学习 对动态规划进行降维打击 写出的压缩数组 自顶向下java写法
public int minDistance(String w1, String w2) {
int r = w1.length()+1, c = w2.length()+1;
int[] dp1 = new int[c];
for(int i = 0; i < c; i++) {
dp1[i] = i;
}
for( int i = 1; i < r; i ++) {
int pre = i-1;
dp1[0] = i;
for ( int j = 1; j < c; j++) {
int temp = dp1[j];
if(w1.charAt(i-1) == (w2.charAt(j-1))) {
dp1[j] = pre;
// dp[i][j] = dp[i-1][j-1];
} else {
dp1[j] = Math.min(Math.min(dp1[j], pre), dp1[j-1]) +1;
// dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) +1;
}
pre = temp;
}
}
return dp1[c-1];
}
【Java版空间压缩代码供参考】 能力有限所以没有实现@dreamer2q 同学的严格O(min(M,N))空间复杂度，不过马虎一下毕竟还是把复杂度降低了一个数量级（
// 空间压缩版代码
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[] dp = new int[n + 1];
for (int j = 0; j <= n; j++) {
dp[j] = j;
}
for (int i = 1; i <= m; i++) {
int pre = i - 1;
dp[0] = i;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (word1.charAt(i-1) == word2.charAt(j-1)) {
dp[j] = pre;
} else {
dp[j] = min(pre, dp[j], dp[j - 1]) + 1;
}
pre = temp;
}
}
return dp[n];
}
private int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
1、根据定义正着解释，两个字符串都可以操作，删除和替换 2、根据作者的倒着来但是 函数的话就倒着解释，dp数组的话就正着解释，只操作s1，增加、插入和删除
