2746. Decremental String Concatenation
Description
You are given a 0-indexed array words
containing n
strings.
Let's define a join operation join(x, y)
between two strings x
and y
as concatenating them into xy
. However, if the last character of x
is equal to the first character of y
, one of them is deleted.
For example join("ab", "ba") = "aba"
and join("ab", "cde") = "abcde"
.
You are to perform n - 1
join operations. Let str0 = words[0]
. Starting from i = 1
up to i = n - 1
, for the ith
operation, you can do one of the following:
- Make
stri = join(stri - 1, words[i])
- Make
stri = join(words[i], stri - 1)
Your task is to minimize the length of strn - 1
.
Return an integer denoting the minimum possible length of strn - 1
.
Example 1:
Input: words = ["aa","ab","bc"] Output: 4 Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: str0 = "aa" str1 = join(str0, "ab") = "aab" str2 = join(str1, "bc") = "aabc" It can be shown that the minimum possible length of str2 is 4.
Example 2:
Input: words = ["ab","b"] Output: 2 Explanation: In this example, str0 = "ab", there are two ways to get str1: join(str0, "b") = "ab" or join("b", str0) = "bab". The first string, "ab", has the minimum length. Hence, the answer is 2.
Example 3:
Input: words = ["aaa","c","aba"] Output: 6 Explanation: In this example, we can perform join operations in the following order to minimize the length of str2: str0 = "aaa" str1 = join(str0, "c") = "aaac" str2 = join("aba", str1) = "abaaac" It can be shown that the minimum possible length of str2 is 6.
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 50
- Each character in
words[i]
is an English lowercase letter
Solutions
Solution 1: Memoization Search
We notice that when concatenating strings, the first and last characters of the string will affect the length of the concatenated string. Therefore, we design a function $dfs(i, a, b)$, which represents the minimum length of the concatenated string starting from the $i$-th string, and the first character of the previously concatenated string is $a$, and the last character is $b$.
The execution process of the function $dfs(i, a, b)$ is as follows:
- If $i = n$, it means that all strings have been concatenated, return $0$;
- Otherwise, we consider concatenating the $i$-th string to the end or the beginning of the already concatenated string, and get the lengths $x$ and $y$ of the concatenated string, then $dfs(i, a, b) = \min(x, y) + |words[i]|$.
To avoid repeated calculations, we use the method of memoization search. Specifically, we use a three-dimensional array $f$ to store all the return values of $dfs(i, a, b)$. When we need to calculate $dfs(i, a, b)$, if $f[i][a][b]$ has been calculated, we directly return $f[i][a][b]$; otherwise, we calculate the value of $dfs(i, a, b)$ according to the above recurrence relation, and store it in $f[i][a][b]$.
In the main function, we directly return $|words[0]| + dfs(1, words[0][0], words[0][|words[0]| - 1])$.
The time complexity is $O(n \times C^2)$, and the space complexity is $O(n \times C^2)$. Where $C$ represents the maximum length of the string.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|