Leetcode 583 Delete Operation for Two Strings

发表于 |

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例 1:
输入: “sea”, “eat”
输出: 2
解释: 第一步将”sea”变为”ea”，第二步将”eat”变为”ea”

说明:
给定单词的长度不超过500。
给定单词中的字符只含有小写字母。

分析：

  1. 因为只能做删除操作，所以这其实就是一个最长公共子序列问题
  2. 定义dp[i][j]表示word1[:i+1]和word2[:j+1]之间的最长公共子序列长度
  3. 递推式如下：
    1. dp[i][j] = dp[i-1][j-1] + 1 if word1[i] == word2[j]
    2. dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  4. 示例中dp数组应如下：
e a t
s 0 0 0
e 1 1 1
a 1 2 2

思路：

  1. 初始化所有的dp[0][j],dp[i][0]
  2. 按照递推式运算
  3. 记l = dp[-1][-1]，则应返回 m-l + n-l，m,n分别代表word1和word2的长度
  4. 处理数据为空的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def minDistance(self, w1, w2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not w1: return len(w2)
        if not w2: return len(w1)
        m,n = len(w1), len(w2)
        dp = [[1]*n for _ in range(m)]
        for i in range(m):
            if w1[i] != w2[0]: dp[i][0] = 0
            else: break
        for j in range(n):
            if w1[0] != w2[j]: dp[0][j] = 0
            else: break

        for i in range(1,m):
            for j in range(1,n):
                if w1[i] == w2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        l = dp[-1][-1]
        return m - l + n - l

1307 / 1307 test cases passed.
diffculty: medium
Runtime: 180 ms