What is the time complexity of the Minimum ASCII Delete Sum for Two Strings problem?

The time complexity is O(m * n), where m and n are the lengths of s1 and s2, respectively, due to the need to fill an m x n dynamic programming table.

What is the key dynamic programming concept used in this problem?

The key concept is state transition, where the problem is broken down into subproblems of calculating the minimum ASCII sum for smaller substrings of s1 and s2.

How does recursion work in the solution?

Recursion is used to calculate the minimum sum for substrings of s1 and s2 by considering whether to delete characters from one or both strings at each step.

What is the role of memoization in solving the Minimum ASCII Delete Sum problem?

Memoization helps store intermediate results to avoid redundant recalculations and significantly improves the efficiency of the solution.

Can the space complexity of the Minimum ASCII Delete Sum problem be optimized?

Yes, by optimizing the dynamic programming table, such as using only two rows or applying space-saving techniques, the space complexity can be reduced from O(m * n) to O(min(m, n)).

#712

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

两个字符串的最小ASCII删除和

给定两个字符串 s1 和 s2 ，返回使两个字符串相等所需删除字符的 ASCII 值的最小和。示例 1: 输入: s1 = "sea", s2 = "eat" 输出: 231 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。在 "eat" 中删除 "t" 并将 …

字符串动态规划

题目描述

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

提示:

1 <= s1.length, s2.length <= 1000
s1 和 s2 由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示使得 $s_1$ 的前 $i$ 个字符和 $s_2$ 的前 $j$ 个字符相等所需删除字符的 ASCII 值的最小和。那么答案就是 $f[m][n]$ 。

如果 $s_1[i-1] = s_2[j-1]$ ，那么 $f[i][j] = f[i-1][j-1]$ 。否则，我们可以删除 $s_1[i-1]$ 或者 $s_2[j-1]$ 中的一个，使得 $f[i][j]$ 达到最小。因此，状态转移方程如下：

f[i][j]= \begin{cases} f[i-1][j-1], & s_1[i-1] = s_2[j-1] \\ min(f[i-1][j] + s_1[i-1], f[i][j-1] + s_2[j-1]), & s_1[i-1] \neq s_2[j-1] \end{cases}

初始状态为 $f[0][j] = f[0][j-1] + s_2[j-1]$ , $f[i][0] = f[i-1][0] + s_1[i-1]$ 。

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

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是 $s_1$ 和 $s_2$ 的长度。

相似题目：

1143. 最长公共子序列

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            f[i][0] = f[i - 1][0] + ord(s1[i - 1])
        for j in range(1, n + 1):
            f[0][j] = f[0][j - 1] + ord(s2[j - 1])
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(
                        f[i - 1][j] + ord(s1[i - 1]), f[i][j - 1] + ord(s2[j - 1])
                    )
        return f[m][n]

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of dynamic programming and state transition techniques.
question_mark
Evaluate the candidate's ability to break down the problem into smaller subproblems and apply recursion.
question_mark
Assess how well the candidate handles base cases and memoization in dynamic programming solutions.

warning

常见陷阱

外企场景

error
Failing to properly handle cases where characters match and not using optimal transitions.
error
Not managing base cases correctly, leading to incorrect calculations in the dp table.
error
Ignoring the need for memoization, which can result in exponential time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
How would the approach change if the strings contained uppercase characters?
arrow_right_alt
What if the characters in the strings were not restricted to lowercase English letters?
arrow_right_alt
Can you optimize the space complexity by reducing the dp table size?

help

常见问题

外企场景

继续练习

#730 统计不同回文子序列 #691 贴纸拼词 #678 有效的括号字符串