#208. Implement Trie (Prefix Tree)

題目描述

一個字典樹(Trie, 讀音"Try")又名前綴樹是一個有效率的字串資料存取的樹狀資料結構。字典樹的資料結構中有非常多的應用功能，像是自動填字與拼字檢查。

請實作字典樹的類別：

Trie()初始化物件。
void insert(String word)插入字串word。
boolean search(String word)如果字串word存在於字典樹中，回傳true，反之回傳false。
boolean startsWith(String prefix)如果如果插入的字串中存在前綴prefix，回傳true，反之回傳false。

限制條件

1 <= word.length, prefix.length <= 2000
word和prefix指會由小寫組成。
測試的命令只會由insert、search和startsWith組成，而且命令數量最多只會有3*10⁴個。

解題思路

Trie的結構其實就是樹，每一筆字串插入後，會被拆分成一個一個的字元，由第一個字元開始連結至下一個字元，直到所有字元串接起來就是Trie。另外在加入字串時，需要給予一個作為字串結尾的判斷條件，這邊使用字元.作為字串結束的標示符號。

在查詢時，需要完整的查詢字串中的所有字元以及結尾標示符，但如果是查詢前綴的話，前綴的結尾不代表字串的結尾，因此不用查詢結尾標示符。

Brute Force

public class Trie {
    public class TreeNode{
        public char CurrentChar;
        public Hashtable Next;
        public TreeNode(char currentChar){
            CurrentChar = currentChar;
            Next = new Hashtable();
        }
    }

    public Hashtable StartChars;

    public Trie() {
        StartChars = new Hashtable();
    }
    
    public void Insert(string word) {
        TreeNode node;
        if(!StartChars.Contains(word[0])) StartChars.Add(word[0], new TreeNode(word[0]));
        node = (TreeNode) StartChars[word[0]];        
        for(int i=1;i<word.Length;i++){
            if(!node.Next.Contains(word[i])) node.Next.Add(word[i],new TreeNode(word[i]));
            node = (TreeNode) node.Next[word[i]];
        }
        if(!node.Next.Contains('.')) node.Next.Add('.',true);
    }
    
    public bool Search(string word) {
        if(!StartChars.Contains(word[0])) return false;
        TreeNode node = (TreeNode) StartChars[word[0]];        
        for(int i=1;i<word.Length;i++){
            if(!node.Next.Contains(word[i])) return false;
            node = (TreeNode) node.Next[word[i]];
        }
        if(!node.Next.Contains('.')) return false;
        return true;
    }
    
    public bool StartsWith(string prefix) {
        if(!StartChars.Contains(prefix[0])) return false;
        TreeNode node = (TreeNode) StartChars[prefix[0]];               
        for(int i=1;i<prefix.Length;i++){
            if(!node.Next.Contains(prefix[i])) return false;
            node = (TreeNode) node.Next[prefix[i]];
        }        
        return true;
    }
}

複雜度分析：

時間複雜度：實作的三個方法的時間複雜度都為O(n)，n為輸入的長度。
空間複雜度：只有void Insert(string word)在最差的情況下，空間複雜度為O(n)，其餘為O(1)。

學習重點

Tree