## 题目描述：

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. `1 <= words.length <= 2000.`
2. `1 <= words[i].length <= 7.`
3. Each word has only lowercase letters.

## 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
``````

## 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()
``````

Pingbacks已关闭。