LeetCode - Implement Trie (Prefix Tree) (Java)

LeetCode – Implement Trie (Prefix Tree) (Java)
Check another space efficent implementation: Ternary Search Tree 三元搜索树
Implement a trie with insert, search, and startsWith methods.

A trie node should contains the character, its children and the flag that marks if it is a leaf node.

class TrieNode {
    char c;
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    boolean isLeaf;
 
    public TrieNode() {}
 
    public TrieNode(char c){
        this.c = c;
    }
}

public class Trie {
    private TrieNode root;
 
    public Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the trie.
    public void insert(String word) {
        HashMap<Character, TrieNode> children = root.children;
 
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
 
            TrieNode t;
            if(children.containsKey(c)){
                    t = children.get(c);
            }else{
                t = new TrieNode(c);
                children.put(c, t);
            }
 
            children = t.children;
 
            //set leaf node
            if(i==word.length()-1)
                t.isLeaf = true;    
        }
    }
 
    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode t = searchNode(word);
 
        if(t != null && t.isLeaf) 
            return true;
        else
            return false;
    }
 
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if(searchNode(prefix) == null) 
            return false;
        else
            return true;
    }
 
    public TrieNode searchNode(String str){
        Map<Character, TrieNode> children = root.children; 
        TrieNode t = null;
        for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            if(children.containsKey(c)){
                t = children.get(c);
                children = t.children;
            }else{
                return null;
            }
        }
 
        return t;
    }
}

http://www.jiuzhang.com/solutions/implement-trie/

 * Your Trie object will be instantiated and called as such:
 * Trie trie = new Trie();
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true

https://discuss.leetcode.com/topic/19221/ac-java-solution-simple-using-single-array

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

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

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

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

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

http://buttercola.blogspot.com/2015/11/zenefits-implement-trie.html
There is a dictionary with words e.g. a, apple, about, book, beats, etc.. 
Design a data structure to support input a prefix string, output the number of words in the dictionary with the same prefix. 
e.g. Input a, return 3, because a, apple, about with the same prefix a
Input ap, only apple has the prefix ap. So return 1

Understand the problem:
The problem clearly suggests to use a trie. The trie should supports at least two operations, 
1. insert(String s);
2. countPrefix(String s)

The challenge part is the second method, i.e. to count the number of words with the same prefix. 

So the solution would be first we implement a method called getPrefix(String s) which returns the pointer of the prefix. Consider how can calculate the number of paths for a binary tree, it equals to the number of leaf nodes. Here is the same. The number of words with the same prefix equals to the number of leaf nodes. So we start from the prefix node, do a DFS recursively until we reach to a leaf node, increment the count, and return. 

public class Trie {

    private TrieNode root;

    private int count = 0;

     

    public Trie() {

        root = new TrieNode();

    }

     

    // Insert a string

    public void insert(String s) {

        TrieNode p = root;

        if (s == null || s.length() == 0) {

            return;

        }

         

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            if (p.children[c - 'a'] == null) {

                    p.children[c - 'a'] = new TrieNode();

            }

             

            if (i == s.length() - 1) {

                p.children[c - 'a'].leaf = true;

            }

             

            p = p.children[c - 'a'];

        }

    }

     

    // Get Prefix, return null if not exist

    public TrieNode getPrefix(String s) {

        if (s == null || s.length() == 0) {

            return null;

        }

         

        TrieNode p = root;

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

             

            if (p.children[c - 'a'] == null) {

                return null;

            } else {

                p = p.children[c - 'a'];

            }

        }

         

        return p;

    }

     

    // Count the number of nodes with the given prefix

    public int countPrefix(String s) {

        TrieNode p = getPrefix(s);

        count = 0;

         

        countPrefixHelper(p);

         

        return count;

    }

     

    private void countPrefixHelper(TrieNode p) {

        if (p.leaf) {

            count++;

        }

         

        for (int i = 0; i < 26; i++) {

            if (p.children[i] != null) {

                countPrefixHelper(p.children[i]);

            }

        }

    }

     

    public static void main(String[] args) {

        Trie trie = new Trie();

         

        Scanner sc = new Scanner(System.in);

         

        while (true) {

            int opCode = sc.nextInt();

            if (opCode == 1) {

                trie.insert(sc.next());

            } else if (opCode == 2) {

                int count = trie.countPrefix(sc.next());

                System.out.println(count);

                break;

            }

        }

         

        sc.close();

    }

}

class TrieNode {

    public TrieNode[] children;

    boolean leaf;

     

    public TrieNode() {

        children = new TrieNode[26];

    }

}

https://leetcode.com/articles/implement-trie-prefix-tree/

Although hash table has $O(1)$ time complexity for looking for a key, it is not efficient in the following operations :

• Finding all keys with a common prefix.
• 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(m \log n)$ time complexity.

Although hash table has $O(1)$ time complexity for looking for a key, it is not efficient in the following operations :

• Finding all keys with a common prefix.
• 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(m \log n)$ time complexity.

class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch -'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }
}

class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }
}

    // search a prefix or whole key in trie and
    // returns the node where search ends
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
           char curLetter = word.charAt(i);
           if (node.containsKey(curLetter)) {
               node = node.get(curLetter);
           } else {
               return null;
           }
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
       TrieNode node = searchPrefix(word);
       return node != null && node.isEnd();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }

Also check Trie Compression - Radix Trie
http://www.ritambhara.in/print-all-words-in-a-trie-data-structure/

1. void printAllWords(TrieNode* root, char* wordArray, int pos = 0)
2. {
3. if(root == NULL)
4. return;
6. if(root->isEndOfWord)
7. {
8. printWord(wordArray, pos);
9. }
10. for(int i=0; i<NO_OF_ALPHABETS; i++)
11. {
12. if(root->child[i] != NULL)
13. {
14. wordArray[pos] = i+'a';
15. printAllWords(root->child[i], wordArray, pos+1);
16. }
17. }
18. }

https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/helpers/Trie.java
public static ArrayList<String> getAllWords(TrieNode n) {
    return getWords(n, "");
}
public static ArrayList<String> getWords(TrieNode n, String prefix) {
    if (prefix == null) return null;
    ArrayList<String> result = new ArrayList<String>();
    char[] characters = prefix.toCharArray();
    for (char ch: characters) {
        if (!n.children.containsKey(ch)) return result;
        n = n.children.get(ch);
    }
    getWords(n, prefix, result);
    return result;
}

private static void getWords(TrieNode n, String word, ArrayList<String> result) {
    if (n.isWord) result.add(word);
    for (char ch : n.children.keySet()) {
        getWords(n.children.get(ch), word + ch, result);
    }
}

http://theoryofprogramming.com/2015/01/16/trie-tree-implementation/
// Prints the 'trieTree' in a Pre-Order or a DFS manner // which automatically results in a Lexicographical Order

X. Trie delete
http://www.geeksforgeeks.org/trie-delete/

http://www.ideserve.co.in/learn/trie-delete

Algorithm requirements for deleting key 'k':
1. If key 'k' is not present in trie, then we should not modify trie in any way.
2. If key 'k' is not a prefix nor a suffix of any other key and nodes of key 'k' are not part of any other key then all the nodes starting from root node(excluding root node) to leaf node of key 'k' should be deleted. For example, in the above trie if we were asked to delete key - "word", then nodes 'w','o','r','d' should be deleted.
3. If key 'k' is a prefix of some other key, then leaf node corresponding to key 'k' should be marked as 'not a leaf node'. No node should be deleted in this case. For example, in the above trie if we have to delete key - "xyz", then without deleting any node we have to simply mark node 'z' as 'not a leaf node' and change its value to "NON_VALUE"
4. If key 'k' is a suffix of some other key 'k1', then all nodes of key 'k' which are not part of key 'k1' should be deleted.
For example, in the above trie if we were to delete key - "xyzb", then we should only delete node "b" of key "xyzb" since other nodes of this key are also part of key "xyz".
5. If key 'k' is not a prefix nor a suffix of any other key but some nodes of key 'k' are shared with some other key 'k1', then nodes of key 'k' which are not common to any other key should be deleted and shared nodes should be kept intact. For example, in the above trie if we have to delete key "abc" which shares node 'a', node 'b' with key "abb", then the algorithm should delete only node 'c' of key "abc" and should not delete node 'a' and node 'b'. 

Base Case:
In this algorithm, we keep on passing the level to the child node starting with level 0 for root node. When this level of the node being looked at matches the length of the key, then we know that the node currently being looked at corresponds to last character of key 'k'. In this case, we check if this node has any children. If it has any children then that means this node must be part of other key(s) as well and hence we cannot delete this node. We simply mark this node as a 'non leaf node' and return deletedSelf = false to the parent node(an example of this case would be deletion of key "xyz"). On the other hand, if this node has no children then we know that this node must be the part of only key 'k', therefore we can safely delete this node. We delete the node(by marking currentNode as null) and return deletedSelf = true to the parent node(an example of this case would be deletion of key "word").
If at any point during the key-path traversal we find out that the currentNode is null then we know that this key was never inserted and hence we return deletedSelf = false by printing out the appropriate message('Key Not Found').

Recursion:
When the current node that we are looking at is not the last node for key 'k', then 
1. We first make a recursive call to delete the node which is child of the currentNode.
2. We check if child node was deleted in step #1. If child node was not deleted then child node must be shared with some other key which implies this currentNode is also part of some other key and hence we do not delete currentNode and return deletedSelf = false to the parent node.    
3. After step #1, if child node was deleted then we check if this currentNode can be deleted. We check that using two conditions: (a) If this node is marked as a leaf node then this node must be the last node corresponding to some other key and hence we return deletedSelf = false without deleting currentNode. (b) If this node has any more children then that means this node is part of some other key as well and hence return deletedSelf = false without deleting currentNode. (c) If both conditions (a) and (b) evaluate to false then we know that this node can be safely deleted. We return deletedSelf = true by marking currentNode as null    

Tricky part:
When we make currentNode = null for deleting the current node, current node won't be deleted since we are making only the local reference to the node as null. Note that this node still has got another reference in terms of parent node's child reference. To delete the node completely, what we do is once a child returns deletedSelf as true, we make child reference = null as well. Code for this is code snippet is -  if (childDeleted) currentNode.children[getIndex(key.charAt(level))] = null;

1	public class Trie {
2
3
4	final static int ALPHABET_SIZE = 26;
5	final static int NON_VALUE = -1;
6
7	class TrieNode
8	{
9	boolean isLeafNode;
10	int value;
11
12	TrieNode[] children;
13
14
15	TrieNode(boolean isLeafNode, int value)
16	{
17	this.value = value;
18	this.isLeafNode = isLeafNode;
19	children = new TrieNode[ALPHABET_SIZE];
20	}
21
22	public void markAsLeaf(int value)
23	{
24	this.isLeafNode = true;
25	this.value = value;
26	}
27
28	public void unMarkAsLeaf()
29	{
30	this.isLeafNode = false;
31	this.value = NON_VALUE;
32	}
33
34	}
35
36	TrieNode root;
37	Trie()
38	{
39	this.root = new TrieNode(false, NON_VALUE);
40	}
41
42	private int getIndex(char ch)
43	{
44	return ch - 'a';
45	}
113	private boolean hasNoChildren(TrieNode currentNode)
114	{
115	for (int i = 0; i < currentNode.children.length; i++)
116	{
117	if ((currentNode.children[i]) != null)
118	return false;
119	}
120	return true;
121	}
122
123	private boolean deleteHelper(String key, TrieNode currentNode, int length, int level)
124	{
125
126	boolean deletedSelf = false;
127
128	if (currentNode == null)
129	{
130	System.out.println("Key does not exist" );
131	return deletedSelf;
132	}
133
134
135	if (level == length)
136	{
137
138
139	if (hasNoChildren(currentNode))
140	{
141	currentNode = null;
142	deletedSelf = true;
143	}
144
145
146	else
147	{
148	currentNode.unMarkAsLeaf();
149	deletedSelf = false;
150	}
151	}
152	else
153	{
154	TrieNode childNode = currentNode.children[getIndex(key.charAt(level))];
155	boolean childDeleted = deleteHelper(key, childNode, length, level + 1);
156
157	if (childDeleted)
158	{
159
160
161	currentNode.children[getIndex(key.charAt(level))] = null;
162
163
164
165	if (currentNode.isLeafNode)
166	{
167	deletedSelf = false;
168	}
169
170
171	else if (!hasNoChildren(currentNode))
172	{
173	deletedSelf = false;
174	}
175
176	else
177	{
178	currentNode = null;
179	deletedSelf = true;
180	}
181	}
182	else
183	{
184	deletedSelf = false;
185	}
186	}
187
188	return deletedSelf;
189	}
190
191	public void delete(String key)
192	{
193	if ((root == null) || (key == null))
194	{
195	System.out.println("Null key or Empty trie error" );
196	return;
197	}
198
199	deleteHelper(key, root, key.length(), 0);
200	return;
201	}
228	}

Read full article from LeetCode – Implement Trie (Prefix Tree) (Java)