单词的压缩编码

难度: Medium

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

words.length == indices.length
助记字符串 s 以 '#' 字符结尾
对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等

给定一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度。

示例 1：

输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"

示例 2：

输入：words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i] 仅由小写字母组成

注意：本题与主站 820 题相同： https://leetcode-cn.com/problems/short-encoding-of-words/

Submission

运行时间: 46 ms

内存: 16.4 MB

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        n = len(words)
        re_words = []
        for word in words:
            re_words.append(word[::-1])

        re_words.sort()

        res = 0
        for i in range(n):
            if i+1< n and re_words[i+1].startswith(re_words[i]):
                pass
            else:
                res += len(re_words[i]) + 1
        return res

Explain

这个题解的核心思路是利用排序和字符串后缀的比较来确定哪些单词是其他单词的后缀。首先，将每个单词逆序，然后对这些逆序后的单词进行排序。排序后，如果某个单词是另一个单词的前缀（由于单词已经逆序，实际上检查的是后缀），则这个单词可以被完全包含在另一个单词的编码中。遍历排序后的单词列表，如果一个单词不是下一个单词的前缀，则它需要单独计入最终的编码字符串中，计算长度时要加上一个字符的空间来放置分隔符'#'。

时间复杂度: O(n log n)

空间复杂度: O(nk)

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        n = len(words)
        re_words = []
        # 逆序所有单词
        for word in words:
            re_words.append(word[::-1])

        # 对逆序后的单词进行排序
        re_words.sort()

        res = 0
        # 遍历排序后的单词，并计算最小编码长度
        for i in range(n):
            # 检查当前单词是否是下一个单词的前缀
            if i+1 < n and re_words[i+1].startswith(re_words[i]):
                pass
            else:
                # 如果不是，计算包括分隔符'#'的长度
                res += len(re_words[i]) + 1
        return res

Explore

逆序单词后排序的主要目的是为了方便检查一个单词是否为另一个单词的后缀。如果直接对原始单词排序，那么排序的结果是基于单词的前缀顺序，这并不利于我们检查后缀关系。逆序后排序使得具有共同后缀的单词会聚集在一起，这样只需要检查当前单词是否为下一个单词的前缀（因为已经逆序，所以前缀检查实际上是后缀检查），从而有效地实现压缩编码。

当逆序单词后，'a' 会变为 'a'，而 'ba' 会变为 'ab'。在对这些逆序后的单词排序时，'a' 会排在 'ab' 前面。在遍历排序后的单词列表进行压缩编码检查时，我们会检查一个单词是否是下一个单词的前缀。在这个例子中，'a' 不是 'ab' 的前缀，所以 'a' 需要被单独计入最终的编码长度。这种处理方式确保了即使单词长度不同，只要它们不是后缀关系，都会被正确处理。

是的，这种方法已经考虑了多个连续单词可能相互包含的情况。通过对逆序后的单词进行排序，任何可以被包含的单词关系都会通过前缀关系表现出来，并且会按照从短到长的顺序排列。在遍历这个排序后的列表时，我们会连续检查每个单词是否是下一个单词的前缀。如果是，则当前单词可以被包含在下一个单词中。如果不是，则当前单词需要单独计入编码长度中。这种方式确保了即使是多个单词相互包含，每个单词都会被正确地处理。