题目描述:
LeetCode 820. Short Encoding of Words
Given a list of words, we may encode it by writing a reference string S
and a list of indexes A
.
For example, if the list of words is ["time", "me", "bell"]
, we can write it as S = "time#bell#"
and indexes = [0, 2, 5]
.
Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.
What is the length of the shortest reference string S possible that encodes the given words?
Example:
Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].
Note:
1 <= words.length <= 2000.
1 <= words[i].length <= 7.
- Each word has only lowercase letters.
题目大意:
给定一组词words,将词语表示成word1#word2#...wordn的形式S。
对于任意词word,都可以找到一个下标i,使得在S中从i开始到最近的#之间的部分与word相等。
求S的最小长度。
解题思路:
解法I 排序
将words中的单词逐一翻转后排序
遍历words,记上一个单词为last,当前单词为word
如果word不以last开始,则将len(last) + 1累计至答案
Python代码:
class Solution(object):
def minimumLengthEncoding(self, words):
"""
:type words: List[str]
:rtype: int
"""
words = sorted(word[::-1] for word in set(words))
ans = 0
last = ''
for word in words + ['']:
if not word.startswith(last):
ans += len(last) + 1
last = word
return ans
解法II 字典树
将word倒序后,插入字典树trie
层次遍历trie,将叶子节点的深度累加即为答案
Python代码:
class TrieNode:
def __init__(self):
self.children = dict()
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for letter in word:
child = node.children.get(letter)
if child is None:
child = TrieNode()
node.children[letter] = child
node = child
def levelOrderTraverse(self):
ans = level = 0
q = [self.root]
while q:
q0 = []
level += 1
for node in q:
if not node.children:
ans += level
else:
q0 += list(node.children.values())
q = q0
return ans
class Solution(object):
def minimumLengthEncoding(self, words):
"""
:type words: List[str]
:rtype: int
"""
words = set(words)
trie = Trie()
for word in words:
trie.insert(word[::-1])
return trie.levelOrderTraverse()
本文链接:http://bookshadow.com/weblog/2018/04/22/leetcode-short-encoding-of-words/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。