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;
	}

	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 data structure.
    public Trie() {
        root = new TrieNode();
    }
    
    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode p = root;
        int index = word.charAt(0) - 'a';

        TrieNode[] nodes = p.getNodes(); 

        for (int i=0; i<word.length(); i++) {
            index = word.charAt(i) - 'a';

            if (nodes[index] == null) {
               nodes[index] = new TrieNode();
            }

            p = nodes[index];
            nodes = p.getNodes();
        }

        p.setEnd(true);
    }
    
    public TrieNode searchPrefix(String word) {
    	TrieNode p = root;
    	TrieNode[] nodes = p.getNodes(); 

        for (int i=0; i<word.length(); i++) {
            int index = word.charAt(i) - 'a';

            if (nodes != null && nodes[index] != null) {
                p = nodes[index];
                nodes = p.getNodes();
            } else {
                return null;
            }
        }

        return p;
    }
    
    // Returns true if the word is in the trie.
    public boolean search(String word) {
        TrieNode p = searchPrefix(word);
        return (p != null && p.isEnd());
    }
    
    // Returns true if there is any word in the trie 
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode p = searchPrefix(prefix);
        return p != 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"));
    }

LeetCode problem

You could easily solve this LeetCode problem after understanding this Trie implementation:

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

Happy programming!

Leave a Reply

Your email address will not be published.