子寒的博客
0%

leetcode583 Delete Operation for Two Strings 解题报告

发表于 更新于 分类于

英文原题

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example

1
2
3
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

分析

    第一次做这个题目的时候完全没有思路。其实这题可以把它看作是求最长公共子序列，那就变成了一道经典的动态规划题。     dp[i][j]表示word1前i个字符与word2前j个字符分别组成的两个前缀字符串的最长公共子串长度，那么dp[0][j]和dp[i][0]都是0。如果word1[x] == word2[y]，那么必存在一个最长公共子串以word1[x]或word2[y]结尾，其他部分等价于word1前x-1个字符和word2前y-1个字符的最长公共子串，即dp[x][y] = dp[x-1][y-1]+1。相对，若 word1[x] != word2[y]，那么它的最长公共子串为word1中前x-1个字符和word2中前y个字符的最长公共子串长度与word1前x个字符和word2前y-1个字符的最长公共子串长度的较大者，于是dp[x][y] = max{dp[x-1][[y], dp[x][y-1]}。     至此递推关系式我们可以得到： dp[i][j] = dp[i-1][j-1]+1;(word1[i]==word2[j]) dp[i][j] = max{dp[i-1][j], dp[i][j-1]}; (word1[i]!=word2[j])

python 代码

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