单词的压缩编码

标签: 字典树 数组 哈希表 字符串

难度: 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] 仅由小写字母组成

Submission

运行时间: 45 ms

内存: 16.4 MB

class Solution(object):
    def minimumLengthEncoding(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        words.sort(key = lambda x: x[::-1])
        ret = 0
        for i in range(len(words)-1):
            if not words[i+1].endswith(words[i]):
                ret+=len(words[i])+1
        ret+=len(words[-1])+1
        return ret

Explain

这个题解的思路是利用字符串排序和后缀匹配来解决问题。首先将所有单词按照反转后的字典序排序，这样可以保证如果一个单词是另一个单词的后缀，那么它一定会出现在那个单词的后面。然后遍历排序后的单词列表，如果当前单词不是下一个单词的后缀，说明当前单词需要被编码，将其长度加1（表示单词结尾的'#'）累加到结果中。最后将最后一个单词的长度加1也累加到结果中，因为最后一个单词一定需要被编码。

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

空间复杂度: O(n)

class Solution(object):
    def minimumLengthEncoding(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        # 将所有单词按照反转后的字典序排序
        words.sort(key = lambda x: x[::-1]) 
        ret = 0
        for i in range(len(words)-1):
            # 如果当前单词不是下一个单词的后缀
            if not words[i+1].endswith(words[i]):
                # 当前单词需要被编码，将其长度加1（表示单词结尾的'#'）累加到结果中
                ret+=len(words[i])+1 
        # 将最后一个单词的长度加1也累加到结果中，因为最后一个单词一定需要被编码
        ret+=len(words[-1])+1 
        return ret

Explore

将单词进行反转再排序的主要目的是将单词的结尾字符放在比较的最前面，这样可以更容易地判断一个单词是否是另一个单词的后缀。在反转后的字典序排序中，如果一个单词是另一个单词的后缀，那么这个单词在排序后的列表中会紧跟在它的超集单词之后。例如，对于单词'apple'和'ple'，反转后分别是'elppa'和'elp'，在字典序中'elp'会排在'elppa'之前。这样排序后只需比较相邻的单词即可确定编码的必要性，简化了后续的处理过程。

由于单词已经按照反转后的字典序进行了排序，如果一个单词是另一个单词的后缀，它必然直接位于那个单词之后。这意味着在检查时只需考虑连续的两个单词。如果检查所有其他单词，不仅增加了不必要的计算复杂度，而且因为排序已经确保了必要的相邻关系，这种全面检查是多余的。

如果有多个单词完全相同，排序过程中这些单词会紧挨在一起。在编码长度计算时，除了最后一次出现的单词需要计入结果（因为它没有后续单词或是其后续单词不是它的后缀），其他相同的单词不会被重复计算，因为它们都会被判定为后续单词的后缀。这样确保了编码的最小长度，避免了重复的单词导致的冗余。

考虑单词列表['time', 'me', 'bell']。经过反转和排序后，列表变为['em', 'emit', 'lleb']。在这个列表中，'em'（对应原单词'me'）不是'emit'（对应原单词'time'）的后缀，因此我们需要单独对'me'进行编码，将其长度加上1（为'#'符号）累加到结果中。这个例子说明了即使单词在原始列表中是另一个单词的后缀，在排序和反转后也可能不再满足这种关系，需要单独编码。