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

0583. 两个字符串的删除操作 #

  • 标签:字符串、动态规划
  • 难度:中等

题目大意 #

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

解题思路 #

动态规划求解。

先定义状态 dp[i][j] 为以 i - 1 为结尾的字符串 word1 和以 j - 1 字结尾的字符串 word2 想要达到相等,所需要删除元素的最少次数。

然后确定状态转移方程。

  • 如果 word1[i - 1] == word2[j - 1]dp[i][j] 取源于以 i - 2 结尾结尾的字符串 word1 和以 j - 1 结尾的字符串 word2,即 dp[i][j] = dp[i - 1][j - 1]
  • 如果 word1[i - 1] != word2[j - 1]dp[i][j] 取源于以下三种情况中的最小情况:
    • 删除 word1[i - 1],最少操作次数为:dp[i - 1][j] + 1
    • 删除 word2[j - 1],最少操作次数为:dp[i][j - 1] + 1
    • 同时删除 word1[i - 1]word2[j - 1],最少操作次数为 dp[i - 1][j - 1] + 2

然后确定一下边界条件。

  • word1 为空字符串,以 j - 1 结尾的字符串 word2 要删除 j 个字符才能和 word1 相同,即 dp[0][j] = j
  • word2 为空字符串,以 i - 1 结尾的字符串 word1 要删除 i 个字符才能和 word2 相同,即 dp[i][0] = i

最后递推求解,最终输出 dp[size1][size2] 为答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        size1 = len(word1)
        size2 = len(word2)
        dp = [[0 for _ in range(size2 + 1)] for _ in range(size1 + 1)]

        for i in range(size1 + 1):
            dp[i][0] = i
        for j in range(size2 + 1):
            dp[0][j] = j

        for i in range(1, size1 + 1):
            for j in range(1, size2 + 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 - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1)

        return dp[size1][size2]
本站总访问量  次  |  您是本站第  位访问者