大家好，今天要來分享的主題是Trie又稱為prefix tree，這個資料結構適合應用在快速搜索、儲存字串。另外在設計和字串相關的功能，例如：自動完成正在輸入的字串、或著拼字檢查...也很適合利用Trie去實作。
而Trie的實作主要使用到hashmap來完成，以下是Trie用來儲存字串的實作示意圖：

首先，Trie是由Trie node組成，每一個節點內有一個hash map和一個判斷儲存的字串是否結束的布林變數（如圖中最上面的長方形所示，之後則簡化了）。
hash map中存放的key會是input的字元，value則是指向另一個新的Trie node。如果在儲存時發現在hash map中已經有儲存相同的key了，就不需要再另外去創造新的Trie Node而是會共用（黑色虛線）。當我們所有需要儲存的字元都存完後會在下一個新的Trie node中將布林變數從初始的False改為True（綠色節點）。

Leetcode 208. Implement Trie (Prefix Tree)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        
        curr.word = True

    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        
        return curr.word

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

上面的startWith，可以將input的字串當成可能已經儲存在Trie中的某些字串的prefix，例如：Trie裡存了"apple", "apply"，則"app"為這兩個單字的preifx，startWith可以去判斷input string是否是某些字串的prefix，因此Trie才又被稱為prefix tree。
這種特性可以實現，平時在瀏覽器上輸入某些字串時，會自動提示一些當紅的搜尋關鍵字。