题目描述：

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

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