题目

在英语中，我们有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。

例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1:

输入: dict(词典) = ["cat", "bat", "rat"]
sentence(句子) = "the cattle was rattled by the battery"
输出: "the cat was rat by the bat"

注:

1. 输入只包含小写字母。
2. 1 <= 字典单词数 <=1000
3. 1 <= 句中词语数 <= 1000
4. 1 <= 词根长度 <= 100
5. 1 <= 句中词语长度 <= 1000

方案

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.

        'bed' -> {
            'b': {
                'e': {
                    'd': {
                        'is_word': True
                    }
                }
            }
        }
        """
        self.lookup = {}


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.lookup
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['is_word'] = True


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.lookup
        for c in word:
            if c not in node:
                return False
            node = node[c]
        # 判断是否是单词
        if 'is_word' in node:
            return True
        return False


class Solution:
    def replaceWords(self, dict: List[str], sentence: str) -> str:
        trie = Trie()
        for d in dict:
            trie.insert(d)

        ret = []
        for word in sentence.split():
            ret.append(word)
            for i in range(1, len(word)):
                if trie.search(word[:i]):
                    ret.pop()
                    ret.append(word[:i])
                    break

        return " ".join(ret)

优化查询流程

class Trie:

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.lookup
        for c in word:
            if c not in node:
                return False
            node = node[c]
        # 判断是否是单词
        if 'is_word' in node:
            return True
        return False


class Solution:
    def buildTrie(self, dicts):
        self.lookup = {}
        node = self.lookup
        for dict in dicts:
            for c in dict:
                if c not in node:
                    node[c] = {}
                node = node[c]
            node['is_word'] = True
            node = self.lookup


    def replaceWords(self, dict: List[str], sentence: str) -> str:
        self.buildTrie(dict)

        ret = sentence.split()
        for i, word in enumerate(ret):
            node = self.lookup
            for j in range(0, len(word)):
                if "is_word" in node:
                    ret[i] = word[:j]
                    break
                elif word[j] not in node:
                    break
                else:
                    node = node[word[j]]

        return " ".join(ret)

原文

https://leetcode-cn.com/explore/learn/card/trie/167/practical-application-i/648/