经典动态规划:编辑距离 :: labuladong的算法小抄 #1054
Replies: 36 comments 8 replies
-
厉害了 |
Beta Was this translation helpful? Give feedback.
-
递归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];
}
} |
Beta Was this translation helpful? Give feedback.
-
DP table版应该再初始一个dp[0][0]=0吧 |
Beta Was this translation helpful? Give feedback.
-
其实插入等价于删除,在字符串1里插入P 等价于在字符串2删除对应的字符。操作只有删除和替换。 |
Beta Was this translation helpful? Give feedback.
-
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] |
Beta Was this translation helpful? Give feedback.
-
东哥 有个图挂了 |
Beta Was this translation helpful? Give feedback.
-
@JackHo327 没有吧,应该是你网络问题 |
Beta Was this translation helpful? Give feedback.
-
东哥,第三个大标题上面的大段代码,关于dp数组的定义,是不是不大对? // 定义:s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i-1][j-1] 莫不是应该写成? // 定义:s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离是 dp[i][j] |
Beta Was this translation helpful? Give feedback.
-
@MathsGo 是我写错了,感谢指出~ |
Beta Was this translation helpful? Give feedback.
-
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];
}
}; |
Beta Was this translation helpful? Give feedback.
-
#递归+备忘录--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) |
Beta Was this translation helpful? Give feedback.
-
自底向上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));
}
}; |
Beta Was this translation helpful? Give feedback.
-
递归解法的复杂度是多少? |
Beta Was this translation helpful? Give feedback.
-
东哥,递归函数中插入的情况,“我直接在s1[i]插入一个和s2[j]一样的字符",有点不理解; |
Beta Was this translation helpful? Give feedback.
-
@NealCou 嗯,你说的有道理,我修改一下表述 |
Beta Was this translation helpful? Give feedback.
-
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];
}
} |
Beta Was this translation helpful? Give feedback.
-
通过学习 对动态规划进行降维打击 写出的压缩数组 自顶向下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];
} |
Beta Was this translation helpful? Give feedback.
-
【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));
}
} |
Beta Was this translation helpful? Give feedback.
-
1、根据定义正着解释,两个字符串都可以操作,删除和替换 2、根据作者的倒着来但是 函数的话就倒着解释,dp数组的话就正着解释,只操作s1,增加、插入和删除 |
Beta Was this translation helpful? Give feedback.
-
如果有跟我一样看的比较蒙的菜鸟,不知道为什么这样操作后就是正确结果,可以综合看看leetcode官方对这一题的题解。https://leetcode.cn/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/ |
Beta Was this translation helpful? Give feedback.
-
打卡打卡 |
Beta Was this translation helpful? Give feedback.
-
打卡,居然把3种操作抽象成下标移动,真的巧妙 |
Beta Was this translation helpful? Give feedback.
-
打卡,从顶到底的递归理解了,但是dp table理解的不到位,感觉有点难啊 |
Beta Was this translation helpful? Give feedback.
-
二刷打卡 |
Beta Was this translation helpful? Give feedback.
-
学到了 |
Beta Was this translation helpful? Give feedback.
-
超级赞,加上前后文,越看越通透!继续加油! |
Beta Was this translation helpful? Give feedback.
-
回溯路径是不是直接看最小编辑距离的dp也可以,不用单独维护一个choice代表操作? |
Beta Was this translation helpful? Give feedback.
-
我觉得能够写出自顶向下的dp函数,就可以写出可能可以压缩的dp数组 |
Beta Was this translation helpful? Give feedback.
-
东哥,为什么我设置s1 = ”apple" s2= "ap",得到的返回值是4呢,按理来说不是只需要删除三次就可以得到ap了吗 |
Beta Was this translation helpful? Give feedback.
-
扩展延申的代码
|
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
文章链接点这里:经典动态规划:编辑距离
评论礼仪 见这里,违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions