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

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

Trie is efficient in finding all keys with a common prefix and enumerating a dataset of strings in lexicographical order.

Another reason why trie outperforms hash table, is that as hash table increases in size, there are lots of hash collisions and the search time complexity could deteriorate to O(n) where n is the number of keys inserted. Trie could use less space compared to Hash Table when storing many keys with the same prefix. In this case using trie has only O(m) time complexity, where m is the key length. Searching for a key in a balanced tree costs O(mlogn) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class TrieNode {
    boolean isEnd;
    TrieNode[] children;
    
    // Initialize your data structure here.
    public TrieNode() {
        isEnd = false;
        children = new TrieNode[26];
    }
    
    public boolean containsKey(char c) {
        return children[c - 'a'] != null;
    }
    
    public void put(char c, TrieNode node) {
        children[c - 'a'] = node;
    }
    
    public TrieNode get(char c) {
        return children[c - 'a'];
    }
    
    public void setEnd(boolean end) {
        isEnd = end;
    }
    
    public boolean isEnd() {
        return isEnd;
    }
}

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) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!cur.containsKey(c)) {
                    cur.put(c, new TrieNode());
                }
                cur = cur.get(c);
            }
            cur.setEnd(true);
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if (word == null) return false;
        
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (! cur.containsKey(c)) return false;
            cur = cur.get(c);
        }
        return cur.isEnd();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (prefix == null) return false;
        
        TrieNode cur = root;
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if (! cur.containsKey(c)) return false;
            cur = cur.get(c);
        }
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");