820. Short Encoding of Words 单词的压缩编码

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

题目地址：https://leetcode-cn.com/problems/short-encoding-of-words/

题目描述

单词数组 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] 仅由小写字母组成

题目大意

给了一个列表，里面保存的是各个单词，现在要看其中的某些单词能不能包括在其他单词里，这样就可以通过指出索引位置的方式压缩字符串的长度。

用#表示字符串的结尾。

要求最短的字符串的长度。

解题方法

倒序+排序

题目让我们使用索引字符串和索引列表能确定所有的单词，索引列表只给出了单词开始的index，而单词结束的位置通过#指出。

所以，如果某个单词s能被单词t包含，那么它必须是t的后缀！如果是后缀,则s可以被压缩。举例：me是time的后缀，因此这两个可以用time#索引字符串的[0,2]索引列表进行压缩。

如果所有单词两两的进行判断是不是后缀，那么总的时间复杂度是O(N^2)，有没有更简单的方法呢？

一个降低时间复杂度的技巧是：如果需要判断的单词都是相邻的就好了！这种情况下，我们只需要遍历一遍就行。那怎么让相同后缀的单词相邻？排序呀！遇事不决先排序！

为了能够通过排序让结尾相同的单词邻近，可以考虑先把单词翻转。（也可以自定义排序函数，按照单词的逆序进行排序）

所以解题方法：

1. 把所有单词进行翻转，并且按照字符序排序，这样相同结尾的单词就会天然弄到了一起。
2. 然后，通过一次遍历，判断前面的单词是不是后面的单词的前缀（已经翻转了），如果不能的话说明前面的单词需要独立成一个新的以#的，所以结果的长度要加上 $len(last)+1$.

举个例子，对于输入：

words = ["time", "me", "bell"]

为了看一个单词能否包含另一个单词，先倒序，在排序，得到：

words = ["em", "emit", "lleb"]

为了能让最后一个单词也进行判断，可以在words末尾添加一个空字符串""。

words = ["em", "emit", "lleb", ""]

从左向右遍历，判断前一个单词是不是后一个单词的前缀，如果是的话就忽略这个单词；否则就拼接上前面这个单词。

得到最终结果emit#lleb#，长度是10。

Python代码如下：

class Solution:
    def minimumLengthEncoding(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        words = sorted([word[::-1] for word in set(words)])
        last = ""
        ans = 0
        for word in words + [""]:
            if not word.startswith(last):
                ans += len(last) + 1
            last = word
        return ans

参考：书影博客

日期

2018 年 7 月 21 日 ———— 买了一个知识星球，要坚持看下去啊～