0648. 单词替换

# 0648. 单词替换#

• 标签：字典树、数组、哈希、字符串
• 难度：中等

## 题目大意 #

• $1 \le dictionary.length \le 1000$。
• $1 \le dictionary[i].length \le 100$。
• dictionary[i] 仅由小写字母组成。
• $1 \le sentence.length \le 10^6$。
• sentence 仅由小写字母和空格组成。
• sentence 中单词的总量在范围 $[1, 1000]$ 内。
• sentence 中每个单词的长度在范围 $[1, 1000]$ 内。
• sentence 中单词之间由一个空格隔开。
• sentence 没有前导或尾随空格。

 1 2 3 4 5 6  输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" 输出："the cat was rat by the bat" 输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" 输出："a a b c" 

## 解题思路 #

### 思路 1：字典树 #

1. 构造一棵字典树。
2. 将所有的词根存入到前缀树（字典树）中。
3. 然后在树上查找每个单词的最短词根。

### 思路 1：代码 #

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50  class Trie: def __init__(self): """ Initialize your data structure here. """ self.children = dict() self.isEnd = False def insert(self, word: str) -> None: """ Inserts a word into the trie. """ cur = self for ch in word: if ch not in cur.children: cur.children[ch] = Trie() cur = cur.children[ch] cur.isEnd = True def search(self, word: str) -> str: """ Returns if the word is in the trie. """ cur = self index = 0 for ch in word: if ch not in cur.children: return word cur = cur.children[ch] index += 1 if cur.isEnd: break return word[:index] class Solution: def replaceWords(self, dictionary: List[str], sentence: str) -> str: trie_tree = Trie() for word in dictionary: trie_tree.insert(word) words = sentence.split(" ") size = len(words) for i in range(size): word = words[i] words[i] = trie_tree.search(word) return ' '.join(words) 

### 思路 1：复杂度分析 #

• 时间复杂度：$O(|dictionary| + |sentence|)$。其中 $|dictionary|$ 是字符串数组 dictionary 中的字符总数，$|sentence|$ 是字符串 sentence 的字符总数。
• 空间复杂度：$O(|dictionary| + |sentence|)$。