資料結構實作: Implement Trie 前綴樹Leetcode #208_精選75題

Luke Richardson on Unsplash

題目敘述

題目已經給定一個Trie前綴樹的類別和相關的函式介面interface，
要求我們把功能實作出來。

Trie() 建構子，初始化一個空的Trie。

void insert(String word)
插入一個新的單字word到Trie裡面。

boolean search(String word)
搜尋word是否存在Trie裡面，假如有，回傳True；如果沒有，回傳False。

boolean startsWith(String prefix)
搜尋prefix前綴是否存在Trie裡面，假如有，回傳True；如果沒有，回傳False。

題目的原文敘述

測試範例

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

約束條件

Constraints:

• 1 <= word.length, prefix.length <= 2000

單字的長度 和 前綴的長度都介於1~2000個字元之間。

• word and prefix consist only of lowercase English letters.

輸入只會有英文小寫字母。

• At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

動態測試時，最多會有三萬次函式呼叫，包含insert(), search(), startWith()

演算法 多層架構 + 字典

其實Trie的結構和Tree很像，差別在於每一層儲存的是鍵值:字元，而映射到的value就是下一層的字典(Python dictionary)。

1.建構子Trie()比較簡單，一開始初始化一個空的字典即可，代表初始化成空的Trie。

2.每當新插入一個單字insert(word)時，就依序把每一個字元從上到下，插入到Trie的多層架構字典中，最後再加上一個"@"當作結尾符號。

為什麼要有結尾符號?

是為了要區別search() 和 startWith()的對應結果。

search()比較嚴格，必須整個字串相同，才算有找到。
而startWith比較寬鬆，只要前綴prefix可以和Trie裡面的任何一個單字的前綴吻合，就算成功。