题目地址: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

参考:书影博客open in new window

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发