Trie – LeetCode Solution [Medium]

Trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

Applications

There are various applications of this special data structure such as :

  1. Autocomplete in mobile and web applications
  2. Spelling checker
  3. Solving word games

and many more.

Implementation

Trie is an efficient information reTrieval data structure and hence the name Trie. It is a special data structure used to store strings. It consists of nodes and edges like a tree. Each node consists of 26 children (including null and non-null values) and each node is connected to its children and parent node. These 26 children are nothing but pointers for each of the 26 letters of the English alphabet. A variable isEnd is used to mark the end of a string present in Trie. This means, combining all the alphabets from root to present character having isEnd = true makes a word, present in Trie.

Strings are stored in a top to bottom manner on the basis of their prefix in a trie. For instance:

Trie
This is an example Trie structure for strings:

["bye", "hear", "here", "hi", "hit"]
Implementing Class for each Trie node
class TrieNode {
 
    //Children nodes
    private TrieNode[] nodes;
 
    //MAX_SIZE = Number of alphabets
    private final int MAX_SIZE = 26;
 
    //To check if it's the last node of a string in Trie
    private boolean isEnd;
     
     
    public TrieNode[] getNodes() {
        return nodes;
    }
 
    public boolean isEnd() {
        return isEnd;
    }
 
    public void setEnd(boolean isEnd) {
        this.isEnd = isEnd;
    }
 
    // TrieNode constructor
    // initializes TrieNode's every new object
    public TrieNode() {
        nodes = new TrieNode[MAX_SIZE];
        isEnd = false;
 
        for (int i=0; i<MAX_SIZE; i++) {
            nodes[i] = null;
        }
 
    }
}
TrieNode class: Each object of this class is representing each node in Trie data structure
Implementing Class for Trie
class Trie {
     
    TrieNode root;
     
    // Initializing TrieNode object
    public Trie() {
        root = new TrieNode();
    }
     
    // Inserts a word into the Trie.
    public void insert(String word) {
    	
        TrieNode node = root;
        int index = word.charAt(0) - 'a';
 
        TrieNode[] nodes = node.getNodes(); 
 
        for (char ch : word.toCharArray()) { 
        	
            index = ch - 'a';
 
            if (nodes[index] == null) {
               nodes[index] = new TrieNode();
            }
 
            node = nodes[index];
            nodes = node.getNodes();
        }
 
        node.setEnd(true);
    }
    
    
     
    public TrieNode searchPrefix(String word) {
    	
        TrieNode node = root;
        TrieNode[] nodes = node.getNodes(); 
 
        for (char ch : word.toCharArray()) { 
        	
            int index = ch - 'a';
 
            if (nodes != null && nodes[index] != null) {
                node = nodes[index];
                nodes = node.getNodes();
            } else {
                return null;
            }
        }
 
        return node;
    }
     
    // Returns true if the word is in the Trie
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return (node != null && node.isEnd());
    }
     
    // Returns true 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;
    }
 
}
Main function to run Trie:
    public static void main(String[] args) {
    	Trie obj = new Trie();
    	obj.insert("word");

    	System.out.println(obj.search("word"));
    }

Time Complexity
Insert: O(n), Search: O(n), n = length of the word

LeetCode problem

You could easily solve this LeetCode problem after understanding this Trie implementation:
Implement Trie (Prefix Tree)

Happy programming!

Leave a Reply

Your email address will not be published. Required fields are marked *