題目
#

leetcode 208 - Implement Trie (Prefix Tree) (題目說明請點連結)

題目簡述
#

實作一個 Trie（前綴樹）資料結構，包含 insert、search 和 startsWith 這三個操作。

範例
#

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

Example 2:

Input
["Trie", "insert", "search", "startsWith"]
[[], ["hello"], ["hello"], ["hel"]]
Output
[null, null, true, true]

Explanation
Trie trie = new Trie();
trie.insert("hello");
trie.search("hello");   // return True
trie.startsWith("hel"); // return True

解題思路
#

這題要求我們實作一個 Trie（前綴樹）資料結構。Trie 是一種多叉樹，每個節點代表一個字符，從根節點到葉節點的路徑構成一個字串。我們需要實作三個主要操作：插入字串、搜尋字串和檢查前綴。

解法
#

定義 TrieNode 類別，包含子節點陣列和標記是否為完整單詞
實作 insert 方法：遍歷字串字符，建立或遍歷節點
實作 search 方法：檢查字串是否存在於 Trie 中
實作 startsWith 方法：檢查是否有以指定前綴開頭的字串

步驟
#

TrieNode 結構：
- 創建 children 陣列，長度為 26（英文字母 a-z）
- 創建 isWord 布林值，標記是否為完整單詞
插入操作：
- 從根節點開始，遍歷字串的每個字符
- 如果字符對應的子節點不存在，創建新的子節點
- 在字串結尾標記 isWord = true
搜尋操作：
- 遍歷字串字符，檢查路徑是否存在
- 檢查最後一個節點的 isWord 標記
前綴檢查：
- 遍歷前綴字符，檢查路徑是否存在
- 如果路徑存在，返回 true

例子說明
#

(root)
 ├─ a
 │   └─ p
 │       └─ p (isWord=true)   ← "app"
 │           └─ l
 │               └─ e (isWord=true)  ← "apple"
 └─ b
     └─ a
         ├─ t (isWord=true)   ← "bat"
         └─ l
             └─ l (isWord=true) ← "ball"

插入字串 “apple” 和 “app”

操作	字串	路徑	結果	說明
insert	“apple”	root → a → p → p → l → e	成功	插入完整字串，標記 e 節點
insert	“app”	root → a → p → p	成功	插入字串，標記第二個 p 節點
search	“apple”	root → a → p → p → l → e	true	路徑存在且 e 節點標記為單詞
search	“app”	root → a → p → p	true	路徑存在且第二個 p 節點標記為單詞
startsWith	“app”	root → a → p → p	true	路徑存在

Trie 結構說明：

根節點：不包含字符，作為所有字串的起點
中間節點：每個節點包含一個字符和 26 個子節點
葉節點：標記 isWord = true 表示從根到該節點構成一個完整單詞

完整程式碼
#

java

class Trie {

    // Trie 節點類別
    class TrieNode {
        TrieNode[] children;    // 子節點陣列，長度為 26（英文字母 a-z）
        boolean isWord;         // 標記是否為完整單詞

        public TrieNode() {
            children = new TrieNode[26]; // 初始化 26 個子節點
            isWord = false;              // 初始化為非單詞
        }
    }

    private TrieNode root;      // Trie 的根節點

    // 建構函數，初始化 Trie
    public Trie() {
        root = new TrieNode();
    }
    
    // 插入字串到 Trie 中
    public void insert(String word) {
        TrieNode node = root;
        
        // 遍歷字串的每個字符
        for(char c : word.toCharArray()){
            int idx = c - 'a';  // 計算字符在陣列中的索引
            
            // 如果字符對應的子節點不存在，創建新的子節點
            if(node.children[idx] == null){
                node.children[idx] = new TrieNode();
            }
            
            // 移動到子節點
            node = node.children[idx];
        }
        
        // 標記最後一個節點為完整單詞
        node.isWord = true;
    }
    
    // 搜尋字串是否存在於 Trie 中
    public boolean search(String word) {
        TrieNode node = root;
        
        // 遍歷字串的每個字符
        for(char c : word.toCharArray()){
            int idx = c - 'a';  // 計算字符在陣列中的索引
            
            // 如果字符對應的子節點不存在，返回 false
            if(node.children[idx] == null){
                return false;
            }
            
            // 移動到子節點
            node = node.children[idx];
        }
        
        // 檢查最後一個節點是否標記為完整單詞
        return node.isWord;
    }
    
    // 檢查是否有以指定前綴開頭的字串
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        
        // 遍歷前綴的每個字符
        for(char c : prefix.toCharArray()){
            int idx = c - 'a';  // 計算字符在陣列中的索引
            
            // 如果字符對應的子節點不存在，返回 false
            if(node.children[idx] == null){
                return false;
            }
            
            // 移動到子節點
            node = node.children[idx];
        }
        
        // 如果能夠遍歷完所有前綴字符，返回 true
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

時間複雜度
#

時間複雜度：
- 插入操作：O(m)，其中 m 是字串長度
- 搜尋操作：O(m)，其中 m 是字串長度
- 前綴檢查：O(m)，其中 m 是前綴長度
空間複雜度：O(26^m)，其中 m 是最長字串的長度
- 每個節點最多有 26 個子節點
- 最壞情況下需要儲存所有可能的前綴組合