How do I solve the Decremental String Concatenation problem?

Use dynamic programming with memoization to minimize the string length after performing join operations between words. Ensure you account for character deletions when the last character of one string matches the first character of the next.

What is the main challenge in the Decremental String Concatenation problem?

The main challenge lies in efficiently minimizing the concatenated string length by correctly handling the join operation and optimizing the order of operations using dynamic programming.

How does dynamic programming help in solving the Decremental String Concatenation problem?

Dynamic programming helps by storing the results of subproblems (minimum string lengths) and avoiding redundant calculations, thus improving the solution's efficiency.

What is memoization in the context of this problem?

Memoization involves storing the results of previously computed DP states so that they can be reused in later calculations, avoiding redundant work and reducing time complexity.

What are some common mistakes to avoid when solving the Decremental String Concatenation problem?

Common mistakes include not handling string deletions correctly, using inefficient brute force approaches, and failing to apply memoization, leading to redundant calculations.

#2746

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

字符串连接删减字母

给你一个下标从 0 开始的数组 words ，它包含 n 个字符串。定义连接操作 join(x, y) 表示将字符串 x 和 y 连在一起，得到 xy 。如果 x 的最后一个字符与 y 的第一个字符相等，连接后两个字符中的一个会被删除。比方说 join("ab", "ba") = "ab…

数组字符串动态规划

题目描述

给你一个下标从 0 开始的数组 words ，它包含 n 个字符串。

定义连接操作 join(x, y) 表示将字符串 x 和 y 连在一起，得到 xy 。如果 x 的最后一个字符与 y 的第一个字符相等，连接后两个字符中的一个会被删除。

比方说 join("ab", "ba") = "aba" ， join("ab", "cde") = "abcde" 。

你需要执行 n - 1 次连接操作。令 str₀ = words[0] ，从 i = 1 直到 i = n - 1 ，对于第 i 个操作，你可以执行以下操作之一：

令 str_i = join(str_{i - 1}, words[i])
令 str_i = join(words[i], str_{i - 1})

你的任务是使 str_{n - 1} 的长度最小。

请你返回一个整数，表示 str_{n - 1} 的最小长度。

示例 1：

输入：words = ["aa","ab","bc"]
输出：4
解释：这个例子中，我们按以下顺序执行连接操作，得到 str₂ 的最小长度：
str₀ = "aa"
str₁ = join(str₀, "ab") = "aab"
str₂ = join(str₁, "bc") = "aabc" 
str₂ 的最小长度为 4 。

示例 2：

输入：words = ["ab","b"]
输出：2
解释：这个例子中，str₀ = "ab"，可以得到两个不同的 str₁：
join(str₀, "b") = "ab" 或者 join("b", str₀) = "bab" 。
第一个字符串 "ab" 的长度最短，所以答案为 2 。

示例 3：

输入：words = ["aaa","c","aba"]
输出：6
解释：这个例子中，我们按以下顺序执行连接操作，得到 str₂ 的最小长度：
str₀ = "aaa"
str₁ = join(str₀, "c") = "aaac"
str₂ = join("aba", str₁) = "abaaac"
str₂ 的最小长度为 6 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 50
words[i] 中只包含小写英文字母。

lightbulb

解题思路

方法一：记忆化搜索

我们注意到，字符串连接时，字符串的第一个字符和最后一个字符会影响到连接后字符串的长度。因此，我们设计一个函数 $dfs(i, a, b)$ ，表示从第 $i$ 个字符串开始连接，且此前已经连接的字符串的第一个字符为 $a$ ，最后一个字符为 $b$ 时，连接后字符串的最小长度。

函数 $dfs(i, a, b)$ 的执行过程如下：

如果 $i = n$ ，说明所有字符串已经连接完毕，返回 $0$ ；
否则，我们考虑将第 $i$ 个字符串连接到已经连接的字符串的末尾或者开头，得到连接后字符串的长度 $x$ 和 $y$ ，则 $dfs(i, a, b) = \min(x, y) + |words[i]|$ 。

为了避免重复计算，我们使用记忆化搜索的方法。具体地，我们使用一个三维数组 $f$ 存储所有的 $dfs(i, a, b)$ 的返回值。当我们需要计算 $dfs(i, a, b)$ 时，如果 $f[i][a][b]$ 已经被计算过，我们直接返回 $f[i][a][b]$ ；否则我们按照上述的递推关系计算 $dfs(i, a, b)$ 的值，并将其存入 $f[i][a][b]$ 中。

在主函数中，我们直接返回 $|words[0]| + dfs(1, words[0][0], words[0][|words[0]| - 1])$ 。

时间复杂度 $O(n \times C^2)$ ，空间复杂度 $O(n \times C^2)$ ，其中 $C$ 表示字符串的最大长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        @cache
        def dfs(i: int, a: str, b: str) -> int:
            if i >= len(words):
                return 0
            s = words[i]
            x = dfs(i + 1, a, s[-1]) - int(s[0] == b)
            y = dfs(i + 1, s[0], b) - int(s[-1] == a)
            return len(s) + min(x, y)

        return len(words[0]) + dfs(1, words[0][0], words[0][-1])

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of dynamic programming and its application to string manipulation.
question_mark
The candidate correctly identifies the state transition process and efficiently computes the minimum length.
question_mark
The candidate uses memoization to avoid redundant calculations, ensuring the solution is optimized.

warning

常见陷阱

外企场景

error
Failing to account for the deletion of characters when joining strings, leading to incorrect length calculations.
error
Using a brute force approach instead of dynamic programming, resulting in inefficient solutions for larger input sizes.
error
Not properly applying memoization, leading to redundant calculations and performance issues.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to handle larger character sets or longer strings.
arrow_right_alt
Introduce additional constraints, such as limiting the number of allowed join operations.
arrow_right_alt
Modify the problem to allow for multiple deletions when joining strings with matching characters.

help

常见问题

外企场景

继续练习

#2707 字符串中的额外字符 #2606 找到最大开销的子字符串 #2900 最长相邻不相等子序列 I