题目描述：

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.

题目大意：

给定一组词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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码