今天要來解的題目是 Leetcode－208. Implement Trie (Prefix Tree)，難度為中等
而我所使用的語言是 python3
壹、理解題目
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true所以說，什麼是 Trie (pronounce "try") 啊？
貳、Prefix Tree - Trie
Trie 又稱作 prefix tree，
之所以取作 Trie 是因為該資料結構能很有效率的取得（reTrieval）資訊，
有什麼用？ Google 的建議查詢就是應用到這個資料結構！
多說無益，直接看圖
像是上圖中的 Trie，共有五個單詞（深黃色的圈代表字尾），分別是 app, apple, car, card, care，
到這裡，你應該能夠推論出，每一個節點（node）最多就只會有 26 個子節點（child node），
因為我們忽略大小寫，所以每個節點所儲存的字元（character）也就只可能有 26 種。
來分析一下時間複雜度吧，
「搜尋／插入／刪除一個單詞」的時間複雜度會直接和該單詞的長度有關係，不難理解，
如果你要找 'apple' 這個單詞（由五個字母組成），你勢必要往下走五個 node 才能找到吧！
所以，時間複雜度 = O(M)，M = 字串長度；
是線性的耶？！這顯然比 BST (binary search tree) 快，
沒錯，但 Trie 所付出的代價是空間的成本，
因為對於任一一個節點，都有 26 種可能，這樣 26x26x26....下去，
如果今天有非常多單詞，這個 Trie 會超龐大！
參、實作 Trie
這題要實作的 function 有 insert, search, 和 startsWith，不用處理刪除，
下圖是 Leetcode 提供的樹幹，要你填滿它！
再看一次上面的 Trie 圖，
顯然 Trie 是由 node 組成的，所以應該創立一個 class
Node 只有兩種，淺黃／深黃色，深黃色代表一個完整的單詞的字尾，
在這裡，我用 is_leave 來表示，因為 leave 在 Tree 的資料結構中通常代表「沒有子節點 的 節點（node）」
self.children 先初始設定為 [None] * 26，因為每個 node 最多就只可能有 26 個小孩嘛～
接著來設計 Trie 的資料結構！
在 __init__() 中，就只要一行，代表此時的 Trie 只有 root，裡面還沒有插入任何單詞
雖然在 Trie 圖中，每個 node 裡面放的是「小寫字母」，
但為了方便起見，可以把 'a' 對應到 0，'b' 對應到 1，... 'z'對應到 25，
如此一來，TrieNode 的 children 才能用 index 去作搜尋，例如：node.children[0] 就代表 'a' 這個 子node，
而這樣的 mapping 可以用一個 function 實現，同樣只要一行就搞定～
肆、實作 function "insert"
接著，來到第一個 function 的實作－insert：
你會怎麼把一個單詞 (word) 插入樹 (Trie) 呢？
一定是從 root 開始往下找吧！
假設，今天我們想要插入 "car" 這個單詞到下面的樹中，
那我們先站在 root 這個節點上，往下看，沒有找到 'c'，
顯然，你需要新增一個 child node 'c' 在 root 之下，同時跳到 'c' 這個節點上，
以此類推，放入 'a' 和 'r'，
最後要記得把最後一個字母 'r' 上色，也就是標示 is_leaf = True，
這樣之後在作搜尋的時候，程式才會知道來到最後一個字母了～
那如果今天要接續插入的字是 'card' 呢？顯然不用再放入 'car' 吧！
所以程式要作檢查，確認子節點是否存在，
也就是站在 'c' node 的時候，想要放入 'a'，那要先檢查 'c' 的子節點中有沒有包含 'a'？
若有，就直接移動到 'a' 節點，若沒有，要先創立好 'a' 節點，才可以跳過去。
（好像在闖關／造路）
程式碼如下，
伍、實作 function "search"
接著是第二個 function－search的實作！
搜尋單詞是否存在於 Trie 之中，有兩種 case：
- 如果今天要找 'ball'，站在 root 節點，第一個字母 'b' 就已經不存在了，那何必繼續往下找呢？
- 今天要找 'ca' 這個詞，但 'a' 並沒有被標記成深黃色，這種情況也不行
所以，要 return True，你勢必要掃過整個詞，並且確認最後一個字母的 node 是被標記成深黃色的
陸、實作 function "startsWith"
最後是第三個 function－startsWith的實作！
這其實跟上一個 function 超像，甚至更簡單，因為這個 function 的概念是在找 prefix，
所以要 return True，你只需要掃過整個詞就好，不用確認最後一個字母的 node 是不是 leave （深黃色）
結果：Accepted！
留言列表
