208. Implement Trie (Prefix Tree)

Implement a trie withinsert,search, andstartsWithmethods.

Example:

Trie trie = new Trie();

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

Thoughts:

1. Design the TrieNode with three field: val, is Word, and Children list.
2. Go through each element and if current letter is not in current node's children set, it means there is currently no record.
3. If found such letter, then check there is a word ending there by accessing the field "isWord".

Code Java

class TrieNode{
    char val;
    boolean isWord;
    TrieNode[] children = new TrieNode[26];
    public TrieNode(){}
    TrieNode(char c){
        val = c;
    }
}

public class Trie {

    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
        root.val = ' ';
    }

    /** Inserts a word into the trie. */
    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(c);
            cur = cur.children[c-'a'];
        }

        cur.isWord = true;
    }

    /** Returns if the word is in the trie. */
    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;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    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;
    }
}

/**
 * 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);
 */

from mlblount45's post