[LeetCode]Short Encoding of Words

题目描述:

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

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

Pingbacks已关闭。

暂无评论

张贴您的评论