leetcode [48] 单词替换

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

在英语中，我们有一个叫做 词根(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 <= 字典单词数 <=1000
1 <=  句中词语数 <= 1000
1 <= 词根长度 <= 100
1 <= 句中词语长度 <= 1000

使用trie建立字典，对于每个词找词根，如果找到一个词根那么替换该词。

class Solution:
    def replaceWords(self, dict: List[str], sentence: str) -> str:
        trie = {}
        for word in dict:
            t = trie
            for w in word:
                if w not in t:
                    t[w] = {}
                t = t[w]
            t[None] = {}
        sentence = sentence.split()
        for i, st in enumerate(sentence):
            t = trie
            for j, w in enumerate(st):
                if w in t:
                    t = t[w]
                    if None in t:
                        sentence[i] = st[: j + 1]
                        break
                else:
                    break
        return ' '.join(sentence)