Implement Trie (Prefix Tree)

Let's say your company wants you to design a module for the search engine that can be used to store and fetch words efficiently. This module will act as a dictionary with insert and search functionalities. Moreover, this dictionary should also have a feature for searching whether a given prefix exists in the dictionary or not. This feature can be represented by the startsWith function because a prefix comes at the beginning of the word.

Let’s say we insert the following words in the dictionary: apple, apricot, app, append, aster, by calling the insertWord() function. Then, by calling the searchWord() function with input, app should return True. Similarly, calling the startsWith() function with the prefix app should also return True.

LeetCode Problem

To implement this with efficient lookup times, we will use a trie data structure. Maybe you had already come to this conclusion, or maybe you were considering using a hash table instead. However, we will not use a hash table for this particular scenario is because it would be very inefficient for the prefix searching. Additionally, scaling hashtables for large datasets also increases collisions and space complexity. On the contrary, a trie is efficient in both time and space.

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

Java Code

class TrieNode {
    char character;
    TrieNode[] children;
    boolean isWordEnding;
    
    public TrieNode(char character) {
        this.character = character;
        children = new TrieNode[26];
        isWordEnding = false;
    }
}

public class Trie {
    TrieNode rootNode;
    public Trie() {
        this.rootNode = new TrieNode(' ');
    }
    
    public void insert(String word) {
        TrieNode tempNode = this.rootNode;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (tempNode.children[index] == null) {
                tempNode.children[index] = new TrieNode(word.charAt(i));
            }
            tempNode = tempNode.children[index];
            if(i == word.length() - 1) {
                tempNode.isWordEnding = true;
            }
        }
    }
    
    public boolean search(String word) {
        TrieNode tempNode = rootNode;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (tempNode.children[index] != null) {
                tempNode = tempNode.children[index];
                if(i == word.length() - 1 && tempNode.isWordEnding) {
                    return true;
                }
            } else {
                return false;
            }
        }
        return false;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode tempNode = rootNode;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (tempNode.children[index] != null) {
                tempNode = tempNode.children[index];
            } else {
                return false;
            }
        }
        return true;
    }
}