• Posts

Problem 208 Implement Trie (Prefix Tree)

Problem Statement

Link - Problem 208

Question

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:

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

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Solution

class TrieNode {
    public:
        TrieNode* links[26];
        bool isLeaf = false;
};

class Trie {
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* temp = root;
        for(char c:word)
        {
            if(!temp->links[c-'a'])
                temp->links[c-'a'] = new TrieNode();
            temp = temp->links[c-'a'];
        }
        temp->isLeaf = true;
    }

    bool search(string word) {
        TrieNode* temp = root;
        for(char c : word)
        {
            if(!temp -> links[c - 'a'])
                return false;
            temp = temp -> links[c - 'a'];
        }
        return temp -> isLeaf;
    }

    bool startsWith(string prefix) {
         TrieNode* temp = root;
        for(char c : prefix)
        {
            if(!temp -> links[c - 'a'])
                return false;
            temp = temp -> links[c - 'a'];
        }
        return true;

    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Complexity Analysis

| Algorithm                 | Time Complexity | Space Complexity |
| ------------------------- | --------------- | ---------------- |
| Trie Insertion and Search | O(m)            | O(m)             |

Explanation

Intial Thoughts

To start, we should think about how we can structure our data to efficiently store and retrieve strings. A tree-like structure comes to mind, where each node represents a character in the string. We can use a root node as the starting point and create child nodes for each subsequent character. This way, we can easily insert new strings, search for existing ones, and check for prefixes. The key is to ensure that our data structure allows for fast lookup and insertion. We can imagine it like a file system, where each directory (node) contains a list of its children (other directories or files). The main considerations are how to handle character storage, node creation, and traversal. We should also think about how to mark the end of a word and how to handle cases where a prefix is not found.

Intuitive Analysis

Intuitively, solving this problem involves creating a mental map of how the trie data structure works. We can think of it like a game of word association, where each character in the string is linked to the next one, forming a path. When we insert a new string, we’re essentially creating a new path from the root to the final character. Searching for a string is like following a path to see if it exists. Checking for a prefix is similar, but we only need to follow the path until we reach the end of the prefix. The main intuition here is to understand how the trie structure allows us to efficiently explore these paths. We can imagine using a ’links’ array to store the child nodes, where each index corresponds to a character in the alphabet. This way, we can quickly traverse the trie and perform the required operations.

1. Intuition

• The problem requires implementing a Trie data structure to store and retrieve strings efficiently
• A Trie is a tree-like data structure where each node represents a string and its children represent prefixes of the string
• The key insight is to use a TrieNode class to represent each node in the Trie, with an array of links to its children and a boolean to indicate if it’s a leaf node
• The Trie class will have methods to insert a string, search for a string, and check if a prefix exists in the Trie
• The insert method will iterate through each character in the string and create new TrieNodes as needed
• The search and startsWith methods will also iterate through each character in the string, but will return false as soon as a non-existent link is found
• The time complexity of these operations will be O(m), where m is the length of the string

2. Implementation

• The TrieNode class is defined with an array links of size 26 to represent the 26 lowercase English letters, and a boolean isLeaf to indicate if the node is a leaf node
• The Trie class has a root node of type TrieNode, which is initialized in the constructor
• The insert method iterates through each character c in the string word, and creates a new TrieNode if the link temp->links[c-'a'] does not exist
• The search method iterates through each character c in the string word, and returns false if the link temp->links[c-'a'] does not exist or if the final node is not a leaf node
• The startsWith method iterates through each character c in the string prefix, and returns false if the link temp->links[c-'a'] does not exist
• The insert, search, and startsWith methods all have a time complexity of O(m), where m is the length of the string
• The space complexity of the Trie is O(n*m), where n is the number of strings and m is the average length of the strings

Complexity Analysis

Time Complexity:

• The time complexity of the Trie operations (insert, search, startsWith) is O(m), where m is the length of the input string. This is because in the worst, average, and best cases, we need to traverse m nodes in the Trie.
• The dominant operations in these methods are the for loops that iterate over each character in the input string, making m the determining factor in the time complexity.
• Mathematically, since we are performing a constant amount of work for each character in the string (comparing the character and moving to the next node), the time complexity can be expressed as O(1) * m = O(m), justifying the Big O classification.

Space Complexity:

• The space complexity of the Trie is O(m) in the worst case, where m is the total number of characters in all the strings inserted into the Trie. This is because each node in the Trie can have up to 26 children (one for each letter of the alphabet), but in the worst case, we only need to store m characters.
• The data structure used to implement the Trie (an array of pointers to child nodes) has a significant impact on the space complexity. Each TrieNode object has an array of 26 pointers, but not all of them are used, leading to some memory waste.
• Justifying the space complexity, we can see that the amount of memory used grows linearly with the total number of characters stored in the Trie, hence the O(m) classification.

Footnote

This question is rated as Medium difficulty.

Similar Questions: