648. Replace Words

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)