648. Replace Words
這一題就屬於一開始看題目比較不容易看出來要是用 Trie ，題目中的一個小提示是最後我們要輸出的字串，是要輸出的是每個單字的 prefix ，看到要找 prefix 後，就可以考慮看看是不是可以用 Trie 來寫。
一開始提到，在 Trie 的問題中，我們很常會需要在節點上面儲存額外的資訊，想是在這個題目裡面，在 Trie 處理一連串來自字典的文字時，很常用到的一個技巧是要記錄字串的節點位置，Trie 有個致命的缺點就是我可以確定這個字串存不存在，可是要還原整個字串並不容易，在這個題目裡面，我直接設立了一個終點的符號 $ 並且把該符號當作 key ，再把字當作 value 存入。
這樣的話當我找到這個字元的時候，我就可以直接找到答案，不用再重新遍歷一次。
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
trie = {}
for word in dictionary:
node = trie
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['$'] = word
ans = []
for word in sentence.split():
node = trie
for char in word:
if char in node:
node = node[char]
# 題目有要求，如果有更短的 prefix ，要選擇該字
if '$' in node:
break
else:
# 題目可能有符合一些 prefix 中的部分 prefix
# 但是沒有完全符合，所以我們直接終結。
break
if '$' in node:
ans.append(node['$'])
else:
ans.append(word)
return ' '.join(ans)