[LeetCode]Replace Words

题目描述:

LeetCode 648. Replace Words

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

  1. The input will only have lower-case letters.
  2. 1 <= dict words number <= 1000
  3. 1 <= sentence words number <= 1000
  4. 1 <= root length <= 100
  5. 1 <= sentence words length <= 1000

题目大意:

英文中,以较短的单词为前缀,可以构成较长的单词。此时前缀可以称为“词根”。

给定一组词根字典dict,一个句子sentence。将句中的单词换为字典中出现过的最短词根。

解题思路:

字典树(Trie)

利用词根dict构建字典树trie,遍历sentence中的word,在trie中进行搜索。

Python代码:

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.isWord = False

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
        node.isWord = True

    def search(self, word):
        ans = ''
        node = self.root
        for letter in word:
            node = node.children.get(letter)
            if node is None: break
            ans += letter
            if node.isWord: return ans
        return word

class Solution(object):
    def replaceWords(self, dict, sentence):
        """
        :type dict: List[str]
        :type sentence: str
        :rtype: str
        """
        trie = Trie()
        for word in dict: trie.insert(word)
        ans = []
        for word in sentence.split():
            ans.append(trie.search(word))
        return ' '.join(ans)

 

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

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

Pingbacks已关闭。

暂无评论

张贴您的评论