從LeetCode學演算法

0208. Implement Trie (Prefix Tree) (Medium)

Question

Implement a trie with insert, search, and startsWith methods.

Example:

1
Trie trie = new Trie();

1
2
3
4
5
6
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

Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

分析/解題

試實作一個trie，當中包含插入，搜尋，是否含前綴判斷的函式。

我們很早以前講過一題使用Trie來進行解題的問題，這次再來複習一下XD
Trie跟樹非常相像，通常用來作字典搜尋，所以又叫做字典樹 。
在實作Trie的時候，我們通常會實作TrieNode作為每個節點的單位，
這當中每個節點主要會記錄兩件事：
1. 這個節點是否到這邊構成一個字
因為可能是經過的節點，比如word -> w, o, r, d，
假設我們插入了一個這樣的字，那麼總共會生成4個節點，
但只有d 這邊應該被判定到此構成一個字 。
所以就這題而言，
我們可以使用一個boolean值(True/False)來儲存這個狀態，
也就是下面程式碼中看到的isWord 。

2. 這個節點往下連接的節點群
以這題來說，由於僅限定a到z，所以我們其實可以用長度為26的節點陣列，
來表達下一個連結。當節點不存在時，表該路徑不存在/尚未生成，
在Java中我們用一個TrieNode[] next來儲存。

但對Python而言，因為語言特性，
我們無法在TrieNode內直接宣告TrieNode(會報錯)，
所以會選擇使用一個字典進行記錄。

最後，留意到由於我們每次進行路徑移動時，
所使用的index要嘛是該字元減去’a’ (Java)，
要嘛乾脆是當前的字元 (Python)，
所以我們不需要額外耗費空間記錄字元值 。
此外，若題目有要求記錄被存入的相同字的次數，
就需要額外的count變數來儲存。(另外可以將isWord改成count用作判斷)

所以整個的思路就會很明顯了：

定義一個TrieNode class，當中有isWord跟next。
在Trie中，初始化時宣告一個根節點root的TrieNode。
insert: 節點從root處開始查找，沿著每個字元連接到下一個TrieNode，
並且如果節點尚未建立就將其建立，走到底後，將isWord設為true。
search: 一樣從root開始，沿著每個字元往下走，
若碰到沒有建立則可直接回傳false。
當走到該節點以後，依據isWord的狀態來判斷要回傳true or false。
startWith: 由於只要路過即可，所以前面和search一樣，
但最後只要能走到，即可回傳true。

Java

Java的部分留意到使用了c - ‘a’的方式來取得index，
因為char是可以當作正整數來相減的。
TrieNode的建構式理論上可省略，
但直接先寫可以降低編譯器還要幫你生成的麻煩，
Submit實測上似乎平均會快一點點XD
(沒有大量測試，有興趣的讀者可再比較看看)
在最開頭的TrieNode代表著根，但它本身並不代表任何字元 ，
請留意這點。

Python

Python的部分額外提供了一個LeetCode上找到解答較快的版本，
是使用#的符號來取代isWord的功能，並用一個多層的字典名為tree，
來記錄整個字典樹的結構。
這個方法的好處是無需另外產生一個TrieNode的物件，
但缺點是必須使用一個不會出現在字串中的符號 。
(如果今天這個字串內會含#的話，這個解就會無法使用了XD)

面試實際可能會遇到的問題

「時間/空間複雜度？」
(插入：O(N)/空間全新的話O(N)
搜尋：O(N)/O(1)
前綴：O(N)/O(1)
當中N代表字串長。)

「如果要支援刪除呢？」
(要實作刪除函式時，不是使用TrieNode的話，
就要留意去處理自己製造的結束標記。
一般使用TrieNode很簡單，使用search找到該字，
並將isWord設成false/False即可。
記得詢問找不到該字要怎麼回傳。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium限額5名優惠(額滿即截止)： https://hiskio.com/courses/319?promo_code=VE9NJQE

問卷抽書＆取得上架通知： https://pse.is/MS2J2
如果你對線上課程不放心，
也可以先來12/17(二) 我在天瓏分享的講座看看！
講座連結： https://pse.is/JS3LJ