[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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

解法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()
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

 

本文链接:http://bookshadow.com/weblog/2018/04/22/leetcode-short-encoding-of-words/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论