题目地址：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
1 2 3 4 5 6 7 8 9 10 11 12 13 14
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发