题目链接：648. 单词替换
两个优化：
- 如果一个词根是另一个词根的词根，那只需要考虑较短的那个词根即可。
- 考虑到词根的长度远小于单词的长度，因此反向匹配，在单词前边从哈希表中查找词根。
from typing import List
class tire(object):
def __init__(self, dictionary: List[str]):
self.roots = set()
self.max_len = 0
for word in sorted(dictionary, key=len):
for i in range(1, len(word) + 1):
if word[:i] in self.roots:
break
else:
self.roots.add(word)
self.max_len = max(len(word), self.max_len)
def root(self, word: str) -> str:
for i in range(1, self.max_len + 1):
if word[:i] in self.roots:
return word[:i]
return word
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
t = tire(dictionary)
return ' '.join(t.root(word) for word in sentence.strip().split())