Implement Trie (Prefix Tree)

Problem Statement

LeetCode-208: A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

1. Trie(): Initializes the trie object.
2. void insert(String word): Inserts the string word into the trie.
3. boolean search(String word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
4. boolean startsWith(String prefix): Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Approach

We will implement the trie using a nested data structure. Each node of the trie will have a collection of 26 pointers, one for each lowercase letter. We will use an array of size 26 to store these pointers. We will also have a boolean variable to mark the end of a word.

class Node{
    private final Node[] children = new Node[26];
    private boolean isLast = false;
    
    Node(){
    }
}

We initialize the trie with an empty root node. The root node will have 26 pointers, one for each lowercase letter.

private final Node root;

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

1. Insert: To insert a word into the trie, we iterate over each character of the word and check if the corresponding pointer is null. If the pointer is null, we create a new node and assign it to the pointer. We continue this process until we reach the end of the word. Finally, we mark the last node as the end of the word.

2. Search: To search for a word in the trie, we iterate over each character of the word and check if the corresponding pointer is null. If the pointer is null, we return false. If we reach the end of the word and the last node is marked as the end of the word, we return true.

3. StartsWith: To check if there is a previously inserted string word that has the prefix prefix, we iterate over each character of the prefix and check if the corresponding pointer is null. If the pointer is null, we return false. If we reach the end of the prefix, we return true.

Implementation

Here is a Java implementation of the trie class:

class Trie {

    class Node{
        private final Node[] children = new Node[26];
        private boolean isLast = false;

        Node(){

        }
    }

    private final Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node itr = root;
        for(char ch : word.toCharArray()){
            if(null == itr.children[ch - 'a']){
                itr.children[ch - 'a'] = new Node();
            }

            itr = itr.children[ch - 'a'];
        }
        itr.isLast = true;
    }
    
    public boolean search(String word) {
        Node itr = root;
        for(char ch : word.toCharArray()){
            if(null == itr.children[ch - 'a']){
                return false;
            }else{
                itr = itr.children[ch - 'a'];
            }
        }

        return itr.isLast;
    }
    
    public boolean startsWith(String prefix) {
        Node itr = root;
        for(char ch : prefix.toCharArray()){
            if(null == itr.children[ch - 'a']){
                return false;
            }else{
                itr = itr.children[ch - 'a'];
            }
        }

        return true;
    }
}

Complexity Analysis

Assuming N is the length of the word:

1. Insert Operation:
   • The time complexity for inserting a word into the trie is $O(N)$.
   • The space complexity is $O(N)$ for storing the word in the trie.
2. Search Operation:
   • The time complexity for searching a word in the trie is $O(N)$.
   • The space complexity is $O(1)$ as we are not using any additional space.
3. StartsWith Operation:
   • Like the search operation, the time complexity for checking if there is a previously inserted string word that has the prefix prefix is $O(N)$.
   • The space complexity is $O(1)$ as we are not using any additional space.