字符串连接删减字母

标签: 数组 字符串 动态规划

难度: Medium

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

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

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

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

  • 令 stri = join(stri - 1, words[i])
  • 令 stri = join(words[i], stri - 1)

你的任务是使 strn - 1 的长度 最小 。

请你返回一个整数，表示 strn - 1 的最小长度。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

Submission

运行时间: 302 ms

内存: 27.2 MB

class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        # dp
        if len(words) == 1:
            return len(words[0])
        words = words[::-1]
        @cache
        def dfs (x: int, l: str, r: str) -> int:
            if x == 0:
                if words[x][0] == r or words[x][-1] == l:
                    return len(words[x]) - 1
                return len(words[x])

            ans1 = len(words[x]) - 1 + dfs(x-1,words[x][0],r) if words[x][-1] == l else len(words[x]) + dfs(x-1,words[x][0],r)
            ans2 = len(words[x]) - 1 + dfs(x-1,l,words[x][-1]) if words[x][0] == r else len(words[x]) + dfs(x-1,l,words[x][-1])
            return min(ans1,ans2)
        
        res1 = len(words[-1]) + dfs(len(words)-2, words[-1][0],words[-1][-1])
        dfs.cache_clear()
        return res1

Explain

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

时间复杂度: O(n * 2500)

空间复杂度: O(n * 2500)

class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        if len(words) == 1:
            return len(words[0])
        words = words[::-1]
        @cache
        def dfs(x: int, l: str, r: str) -> int:
            if x == 0:
                return len(words[x]) - 1 if words[x][0] == r or words[x][-1] == l else len(words[x])
            ans1 = len(words[x]) - 1 + dfs(x-1, words[x][0], r) if words[x][-1] == l else len(words[x]) + dfs(x-1, words[x][0], r)
            ans2 = len(words[x]) - 1 + dfs(x-1, l, words[x][-1]) if words[x][0] == r else len(words[x]) + dfs(x-1, l, words[x][-1])
            return min(ans1, ans2)
        res1 = len(words[-1]) + dfs(len(words) - 2, words[-1][0], words[-1][-1])
        dfs.cache_clear()
        return res1

Explore

数组反转的目的在于简化动态规划过程中的状态转移。通常，动态规划需要从一个基本状态逐步构建到最终状态。在这个问题中，如果不进行反转，我们需要从前向后考虑字符串的连接，这将涉及到更复杂的状态追踪，特别是在字符串较多时。反转后，我们可以从后向前计算，使得每次递归调用都是基于已经计算过的结果，简化了问题的复杂度。

`l`和`r`在`dfs`函数中代表当前连接字符串序列的最左侧和最右侧的字符。这两个参数帮助确定当前处理的字符串是否可以与已有的字符串序列在左端或右端减少字符进行连接。例如，如果当前字符串的末尾字符与`l`相匹配，那么在连接到序列左端时可以少计算一个字符长度，因为这两个字符重叠。同理适用于`r`。这样的设计使得算法在连接时能够有效地考虑减少重复字符，优化整体字符串的长度。

在`dfs`函数中，如果`words[x][0] == r`或`words[x][-1] == l`，则表示当前字符串可以在连接点与另一字符串重叠一个字符。具体到代码实现，这会导致在计算连接长度时直接减去一个字符（长度减1）。例如，如果`words[x][-1] == l`，当将`words[x]`连接到左侧时，不需要重复计算`l`字符，因此实际添加到序列的长度是`len(words[x]) - 1`。这一机制在动态规划中被用于寻找可能的最短总长度。

`l`和`r`的可能值最多50种通常指的是字符种类的限制，而非字符串的长度。这意味着假设在使用的字符集中，字符的种类不超过50种（如英文字母的大小写共52种）。在算法中，每个字符的位置可以由一个固定种类的字符来表示，所以`l`和`r`作为单个字符，其可能的值受到字符集大小的限制。这不限制单个字符串的长度，而是限制了考虑的字符种类，确保缓存的有效和实用性。