How do I approach the Delete Operation for Two Strings problem?

Use dynamic programming to compute the longest common subsequence (LCS), then subtract twice the LCS length from the total length of the strings to find the minimum deletions.

What is the time complexity of the Delete Operation for Two Strings problem?

The time complexity is O(m * n), where m and n are the lengths of the two strings.

What are the key steps in solving the Delete Operation for Two Strings problem?

First, compute the longest common subsequence (LCS) using dynamic programming. Then calculate the minimum deletions as the sum of the lengths of the two strings minus twice the LCS length.

What is the space complexity of this problem?

The space complexity is O(m * n) due to the DP table storing the LCS values.

Can I optimize space for the Delete Operation for Two Strings problem?

Yes, you can reduce the space complexity by storing only the current and previous rows of the DP table instead of the entire table.

#583

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。示例 1：输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将…

字符串动态规划

题目描述

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

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

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示使得字符串 $\textit{word1}$ 的前 $i$ 个字符和字符串 $\textit{word2}$ 的前 $j$ 个字符相同的最小删除步数。那么答案为 $f[m][n]$ ，其中 $m$ 和 $n$ 分别是字符串 $\textit{word1}$ 和 $\textit{word2}$ 的长度。

初始时，如果 $j = 0$ ，那么 $f[i][0] = i$ ；如果 $i = 0$ ，那么 $f[0][j] = j$ 。

当 $i, j > 0$ 时，如果 $\textit{word1}[i - 1] = \textit{word2}[j - 1]$ ，那么 $f[i][j] = f[i - 1][j - 1]$ ；否则 $f[i][j] = \min(f[i - 1][j], f[i][j - 1]) + 1$ 。

最终返回 $f[m][n]$ 即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是字符串 $\textit{word1}$ 和 $\textit{word2}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            f[i][0] = i
        for j in range(1, n + 1):
            f[0][j] = j
        for i, a in enumerate(word1, 1):
            for j, b in enumerate(word2, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1
        return f[m][n]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate understands dynamic programming concepts like state transitions and recursive relations.
question_mark
The candidate should explain how they arrived at the minimum deletions by subtracting the LCS length from the total string lengths.
question_mark
The candidate can efficiently describe time and space complexity in terms of the problem's constraints.

warning

常见陷阱

外企场景

error
Confusing the problem with a subsequence matching problem without considering deletions.
error
Overcomplicating the dynamic programming table and not explaining the base cases properly.
error
Not considering edge cases like empty strings or strings with no common characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variant 1: Finding the minimum steps to make the strings equal by inserting characters.
arrow_right_alt
Variant 2: Extending this problem to consider insertions and deletions to make two strings identical.
arrow_right_alt
Variant 3: Modifying the problem to allow character replacements in addition to deletions.

help

常见问题

外企场景

继续练习

#639 解码方法 II #647 回文子串 #516 最长回文子序列