648. 单词替换

Difficulty
Medium
Tags
前缀树
URL
https://leetcode-cn.com/problems/replace-words/
Star
在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子。
示例 1：
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
示例 2：
输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"
提示：
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写字母组成。
  • 1 <= sentence.length <= 10^6
  • sentence 仅由小写字母和空格组成。
  • sentence 中单词的总量在范围 [1, 1000] 内。
  • sentence 中每个单词的长度在范围 [1, 1000] 内。
  • sentence 中单词之间由一个空格隔开。
  • sentence 没有前导或尾随空格。
通过次数24,465提交次数41,285

法 1 前缀树

思路
对字典进行排序.
之前是根据前缀查找单词，现在是根据单词查找字典树上的前缀。
题解
class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = Trie()
        dictionary.sort()
        for word in dictionary:
            trie.insert(word)

        sentence = sentence.split()
        for i in range(0, len(sentence)):
            sentence[i] = trie.prefix(sentence[i])

        return " ".join(sentence)



class Trie:
    def __init__(self):
        self.root = {}
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
						# 此处要及时停止
            if "word" in node:
                return 
        node["word"] = word
    
    def prefix(self, word):
        """
        返回该单词的前缀，如果存在的话
        """
        node = self.root
        for c in word:
            if c not in node:
                break
            node = node[c]
        
        return node["word"] if "word" in node else word