代码随想录算法训练营第五十二天| LeetCode1035.不相交的线、583. 两个字符串的删除操作、72. 编辑距离

1035.不相交的线

题目描述: 1035.不相交的线.

解法

二维dp

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

思路就是，相等的话不用操作，不相等的话，删除1，删除2，或者都删除，但是每次删除都要计数。
注意初始化。

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

题目描述: 583. 两个字符串的删除操作.

解法

二维dp

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

考虑这个过程 ，如果两个不相等，可以删除一个，可以删除两个，或者都删除，不用考虑删除完了会不会还是不相等的，因为上一个状态一定是相等的。

72. 编辑距离

题目描述: 72. 编辑距离.

解法

二维dp

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

一个单词的增加，就是等同于另一个单词的删除，替换的话就是从dp[i-1][j-1]新增一个操作即可。