Basic Trie

TireNode Definition

class TrieNode {
    
    public TrieNode[] children = new TrieNode[26];
    public boolean isWord; 

    // public char val;    // normally not necessary
    /* normally not necessary
    TrieNode(char c) {
        this.val = c;
    }
    */
}

Trie 類中：
定義root:

private TrieNode root = new TrieNode();

Trie primary methods:

(1) void insert(String word) (or called addWord)
time complexity: O(LenOfWord)
(2) boolean search(String word)
time complexity: O(LenOfWord)
(3) boolean startsWith(String prefix)
time complexity: O(LenOfWord)

Space Complexity: O(number of nodes)

Implementation

(1) insert

public void insert(String word) {
    TrieNode cur = root;
    for(int i = 0; i < word.length(); i++){
        char c = word.charAt(i);
        if(cur.children[c - 'a'] == null){
            cur.children[c - 'a'] = new TrieNode();
        }
        cur = cur.children[c - 'a'];
    }
    cur.isWord = true;
}

(2) search
a. Iterative解法

public boolean search(String word) {
    TrieNode cur = root; 
    for(int i = 0; i < word.length(); i++){
        char c = word.charAt(i);
        if(cur.children[c - 'a'] == null) return false;
        cur = cur.children[c - 'a'];
    }
    return cur.isWord;
}

b. recursive dfs解法

public boolean search(String word) {
        return search_helper(word, 0, root);
    }
    
    private boolean search_helper(String word, int start, TrieNode node) {
        if (start == word.length()) return node.isWord;   
        char c = word.charAt(start);
        return node.children[c - 'a'] != null && search_helper(word, start + 1, node.children[c - 'a']);
    }

(3) startsWith

public boolean startsWith(String prefix) {
    TrieNode cur = root; 
    for(int i = 0; i < prefix.length(); i++){
        char c = prefix.charAt(i);
        if(cur.children[c - 'a'] == null) return false;
        cur = cur.children[c - 'a'];
    }
    return true;
}

Example:

208 Implement Trie (Prefix Tree) http://www.reibang.com/p/cb6f8adb5b8a
211 Add and Search Word - Data structure design http://www.reibang.com/p/4389a50968b5