題目出處
208. Implement Trie (Prefix Tree)
難度
medium
個人範例程式碼
class TrieNode:
def __init__(self):
self.children = {}
self.hasword = False # only True if exist word,
# apple in dict, but app not in, False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.hasword = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.hasword
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.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)
算法說明
資料結構設計類型的題目，考的就是設計資料結構的能力，比較難。
這邊要實作的有三個功能，startsWith, search, insert，
我們先來了解 Trie (字典樹)
Trie (字典樹) 是用來特化搜尋「前綴文字 Prefix」用的資料結構，
特色就是我們把每個單字建成一個樹狀，而當我們搜尋一個前綴字時，能夠快速順著字典往下，
一個 TrieNode 會有，
- childrens：紀錄往下的字母
- hasword：到此本身是否有這個文字
特別注意 hasword 的功能，例如 apple 在字典中，
但沿著路徑我們會搜尋到 app，為了反映 app 這個字不屬於字典的字，
我們用 hasword 來記錄這個點。(apple 紀錄在 e 上，app 如果有，會記錄在最後一個 p 上。)Trie (字典樹) 範例圖
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
x
Boundary conditions
注意搜尋的過程中，有時候可以有搜尋到路徑，但實際上沒有那個文字，所以我們會需要 hasword 這個 bool，
例如我們有 apple 在 Trie 中，
沿路會看到 app，但不表示搜尋到 app 就有 app 這個字。
