代码随想录算法训练营第56天 | 编辑距离

代码随想录系列文章目录

动态规划篇 —— 编辑距离

---

---

583. 两个字符串的删除操作

题目链接
这个题就是编辑距离，可以增 可以删 的情况 少了一种替换的情况

1.状态定义

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

2.状态转移

还是分两种 一种是 Word[i-1] == Word[j-1] ,这种就不需要做删除操作
dp[i][j] = dp[i-1][j-1]

一种是 Word[i-1] != Word[j-1]
这种情况要么是 删除Word[i-1], 要么是删除Word[j-1] 都需要一个操作次数
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

3 base case

还是两种情况dp[i][0] 和 dp[0][j], 都是把一方全删完，那么操作次数就是另一方的长度

4遍历顺序以及解的位置

正序
解的位置就是dp[m][n], m位的子串1和n位的子串2删除成一样的最小操作次数

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
                else: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
        return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

72. 编辑距离

题目链接
这个题就是完整版的编辑距离，和上面的过程基本一样，多了一种替换字母的情况

重点写一下状态转移
两种情况
word[i-1] == word[j-1] : dp[i][j] = dp[i-1][j-1]
此时不用做操作，直接由上一个状态变过来，不需要增加操作次数

word[i-1] != word[j-1] :
增、删
替换

增删是一种情况，因为给字符串2增一个就相当于给字符串1删一个，不如全理解为删
要么删s1, 要么删s2, 删完之后加上一个操作次数1

dp[i-1][j] + 1, dp[i][j-1] + 1
1

替换是另一种情况，由dp[i-1][j-1]转化来，加一个替换的操作次数

dp[i-1][j-1] + 1
1

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
                else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

编辑距离题目总结

文章链接