208. Implement Trie (Prefix Tree)

Question: Implement Trie (Prefix Tree)

Solution

Trie 字典樹

如下圖，先了解 Trie 字典樹是什麼，再開始解題

Trie 概念架構

ref: system design interview chapter 13

Trie 由一個個節點組成，因此我們還需要 TrieNode

Trie 的第一個節點 root (TrieNode) 可以 mapping 到每一個字母，所以 TrieNode 中需要一個 children 字典 {}

Insert

當有字要插入時，先看他第一個字母是否存在 root 的 children 中，如果不存在，就在 children 的字典中幫他建立該字母的 key，值為 TrieNode。

舉例：

插入 apple ，root 就要鍵入 “a”，值放下一個字母的 TrieNode → {”a”: p 的 TrieNode()}，再移動到 p TrieNode，建立 p TrieNode；移動到 p TrieNode，建立 l TrieNode；移動到 l TrieNode，建立 e TrieNode，移動到 e TrieNode，給他一個 end_of_word 的 mark

插入 bike，root 就要鍵入 “b”， 值放下一個字母的 TrieNode → {”a”: p 的 TrieNode(), “b”: i 的 TrieNode()}

Search

當要尋找一個字時，就從 root 開始找第一個字母

• 如果沒有：return False
• 如果有：mapping 到該 TrieNode 後，繼續去看下一個字母
• 全部看完以後，看最後一個字是不是「結尾字母」，因此 TrieNode 還要具備一個 attribute: end_of_word = True/False
  是: return True，不是的話: return False

舉例：

搜尋 apple，從 root 的 TrieNode 開始看有沒有 “a”，有的話移動到 a TrieNode，繼續看有沒有 “p”，有的話移動到 p TrieNode，繼續看有沒有 “p”，有的話移動到 p TrieNode，繼續看有沒有 “l”，有的話移動到 l TrieNode，繼續看有沒有 “e”， 有的話移動到 e TrieNode，因為是最後一個字母，所以要回傳他「是否為最後一個字母」: return end_of_word 即可

StartWith

跟 Search 很像，但是不需要看最後一個字是不是 end_of_word，直接 return True 即可

class TrieNode:

def __init__(self):

self.children = dict()

self.end_of_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.end_of_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.end_of_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)

Video Solution