2.20 Implement Trie

Description

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

Note: You may assume that all inputs are consist of lowercase letters a-z.

Method

implement trie with trienode array as children, use the char index as children index

Time and Space Complexity

o(n) n is average lenght of the word

Code

 class TrieNode {
// Initialize your data structure here.
TrieNode[] children;
boolean isLeaf;

public TrieNode() {
    children = new TrieNode[26];
}
}


public class Trie {

private TrieNode root;

public Trie() {
    root = new TrieNode();
}

// Inserts a word into the trie.
public void insert(String word) {
       if (word == null || word.length() == 0){
           return;
       }

       TrieNode node = root;
       TrieNode[] children;
       for (int i = 0; i < word.length(); i++){
            children = node.children;
            char c = word.charAt(i);
            if (children[c - 'a'] != null){
                node = children[c - 'a'];
            } else {
                TrieNode newnode = new TrieNode();
                children[c - 'a'] = newnode;
                node = newnode;
            }

            if (i == word.length() - 1){
                node.isLeaf = true;
            }
       }
}

// Returns if the word is in the trie.
public boolean search(String word) {
       if (word == null || word.length() == 0){
           return false;
       }
       TrieNode node = root;
       TrieNode[] children;
       for (int i = 0; i < word.length(); i++){
            children = node.children;
            char c = word.charAt(i);
            if (children[c- 'a'] != null){
                node = children[c - 'a'];
            } else {
                return false;
            }

            if (i == word.length() - 1){
                return node.isLeaf;
            }
       }
       return true;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
       if (prefix == null || prefix.length() == 0){
           return false;
       }
       TrieNode node = root;
       TrieNode[] children;
       for (int i = 0; i < prefix.length(); i++){
            children = node.children;
            char c = prefix.charAt(i);
            if (children[c- 'a'] != null){
                node = children[c - 'a'];
            } else {
                return false;
            }
       }
       return true;
}

}