字符串连接删减字母

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

/* 思路：使用 Java Stream API 实现相同的逻辑。我们通过计算每次 join 操作后的字符串长度，并在流操作中选择最小的长度。 */

import java.util.stream.IntStream;

public class SolutionStream {
    public int minimizeStringLength(String[] words) {
        int n = words.length;
        return IntStream.range(1, n)
                .map(i -> Math.min(words[i - 1].length() + words[i].length() - (words[i - 1].charAt(words[i - 1].length() - 1) == words[i].charAt(0) ? 1 : 0),
                                  words[i].length() + words[i - 1].length() - (words[i].charAt(words[i].length() - 1) == words[i - 1].charAt(0) ? 1 : 0)))
                .reduce(words[0].length(), Integer::sum);
    }
}

这个题解使用了递归的动态规划方法来解决问题。首先将words数组反转，然后从后向前进行动态规划。使用带缓存的深度优先搜索（DFS）来计算每一步连接操作的最小可能长度。定义dfs函数，其中x表示当前处理的words数组的索引，l和r分别表示当前字符串连接的左侧和右侧可能的匹配字符。如果当前字符串的末尾字符与l匹配，或者起始字符与r匹配，则在连接时可以减少一个字符。对于每个字符串，计算两种连接方式（当前字符串连接到已有字符串的左边或右边）的最小长度，返回这两种方式的最小值。

O(n * 2500)

O(n * 2500)