Implement Trie (Prefix Tree)

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

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

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

 class TrieNode {

   
    private TrieNode[] nodeLinks;
    public boolean isEnd;

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

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

class Trie {

    /** Initialize your data structure here. */
    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.isEnd = true;
    }
   
    private TrieNode searchWordInLinks(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 = searchWordInLinks(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 = searchWordInLinks(prefix);
        return node != null;
    }
}

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

Try it on Leetcode

Click here to read about Trie

Here, we are using arrays concept.

TrieNode

TrieNode class describes about data structure we used in this problem. In this we are creating array of TrieNode for storing links called as nodeLinks. isEnd boolean , if it is true, then the link continues and it has another extra character node and if it is false, then there is no links and it is the end.

In each operation we are doing subtract with 'a' to start storing each character at index 0 [i.e., a at 0, b at 1 and goies on..] . For this reason, we are initialising, each TrieNode as length of 26

containsKey(char ch)

If any character is present, (i.e., not null), it returns true. If particular character is null, then it returns false.

get(char ch)

It is used to return the node details of particular character.

put(char ch, TrieNode node)

It is used to add each character along with its node details in the overall nodeLinks.

insert(String word) in Class Trie

Class Trie constructor has a creation of new TrieNode.

We insert a key by searching into the trie. We start from the root and search a link, which corresponds to the first key character. There are two cases :

• A link exists. Then we move down the tree following the link to the next child level. The algorithm continues with searching for the next key character.
• A link does not exist. Then we create a new node and link it with the parent's link matching the current key character. We repeat this step until we encounter the last character of the key, then we mark the current node as an end node and the algorithm finishes.

search(String word)

In this we call searchWordInLinks() method  to check whether entire string is present or not. In this method, each character calls conatinsKey to check occurrences of character.

 a) If anyone of character is not present in nodeLinks then it will returns null or if there is no end [isEnd - false] it will be false.

 b) If all characters are found and isEnd is true, then search string is found.

startsWith(String word)

Here we are using same steps in above search() method. And another note is, here there is no need to check for isEnd condition. Because we need to check, if given particular string is present in node or not is enough.

Like previous method, we are iterating each character from given string. If any of given charcter is not found, it returns null and startsWith() will return false. If all characters are found, then method returns true.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation


Please let us know your views in comment section

Subscribe us to receive updates instantly..

Happy Coding..!!