两个字符串的删除操作

Leetcode Link: 583. 两个字符串的删除操作 - 力扣（LeetCode）

题目

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

从暴力递归到动态规划

这道题和最长公共子序列基本思路一样，不过我们这里直接来思考该题

暴力递归

典型的样本对应模型，考虑两个样本[0.. i]和[0.. j]上的最小步数，思考和 i-1, j-1 的这种关系

显然，存在下面三种可能性

1. 相同的子串可能以 i 结尾，一定不以 j 结尾，那么就需要删除 j 位置的元素，即步数+1
2. 相同的子串可能以 j 结尾，一定不以 i 结尾，那么就需要删除 i 位置的元素，即步数+1
3. 相同的字串一定以 i 和 j 结尾，则一步也不走，所需的最小步数=process (i-1, j-1)

下面思考 base case，可能有点绕

1. 当 i==0 时，如果 word1[i] 在当前的 word2 的[0.. j]中 (含 j)，则一定需要将 word2 [0.. j]删除到只剩那一个元素，即走 j 步；反之则需要把 word1 [0] 和 word2 [0.. j] 全部都删掉，得到空子串后两者才能相等，即走 j+2 步 (j+1 步删掉 word2，1 步删掉 word1)
2. 当j==0时，分析同上

代码超时

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        @functools.lru_cache()
        def process(i, j):
            if i == 0:
                if word1[i] in word2[0:j+1]:
                    return j
                else:
                    return j+2
            if j == 0:
                if word2[j] in word1[0:i+1]:
                    return i
                else:
                    return i+2
 
            p1 = process(i-1, j) + 1
            p2 = process(i, j-1) + 1
 
            p3 = float('inf')
            if word1[i] == word2[j]:
                p3 = process(i-1, j-1)
            return min(p1, p2, p3)
        return process(len(word1)-1, len(word2)-1)

动态规划

直接改，注意 dp 表更新顺序以及 base case

一般格子(i, j)依赖左、左上、上，基于base case可以直接从左到右，从上到下进行更新。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for _ in range(len(word2))] for _ in range(len(word1))]
        for j in range(len(word2)):
            if word1[0] in word2[0:j+1]:
                dp[0][j] = j
            else:
                dp[0][j] = j+2
        for i in range(len(word1)):
            if word2[0] in word1[0:i+1]:
                dp[i][0] = i
            else:
                dp[i][0] = i+2
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                p1 = dp[i-1][j] + 1
                p2 = dp[i][j-1] + 1
                p3 = float('inf')
                if word1[i] == word2[j]:
                    p3 = dp[i-1][j-1]
                dp[i][j] = min(p1, p2, p3)
        return dp[len(word1)-1][len(word2)-1]

可以做状态压缩吗？

启发和联系