algoadvance

Leetcode 208. Implement Trie (Prefix Tree)

Problem Statement

Implement a trie with insert, search, and startsWith methods.

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and search a set of strings, where the keys are usually strings. The main operations of a trie are:

• insert(string word): Inserts the string word into the trie.
• search(string word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• startsWith(string prefix): Returns true if there is any string in the trie that starts with the given prefix, and false otherwise.

Clarifying Questions

1. Character Set: Do the strings only contain lowercase English letters?

   Assumption: Yes, strings only contain ‘a’ to ‘z’.

2. Case Sensitivity: Are the strings case-sensitive?

   Assumption: No, we can assume the strings are lowercase for simplicity.

3. Operations Frequency: Will any operation (insert, search, startsWith) be called more frequently than others?

   Assumption: No specific operation is highlighted as being more frequent.

Strategy

Trie Node Structure

Each node in a Trie will contain:

• An array of pointers (or a map) to its children.
• A boolean to mark the end of a word.

Insert Operation

• Traverse each character in the word.
• If the child node for that character doesn’t exist, create it.
• Move the current pointer to the child node.
• After the entire word is traversed, mark the end of the current node as true.

Search Operation

• Traverse each character in the word.
• If the child node for that character doesn’t exist, return false.
• If the traversal completes and the current node is marked as the end of a word, return true.

startsWith Operation

• Traverse each character in the prefix.
• If the child node for that character doesn’t exist, return false.
• If the traversal completes, return true.

Code

#include <iostream>
#include <vector>

using namespace std;

class TrieNode {
public:
    bool isEndOfWord;
    vector<TrieNode*> children;
    
    TrieNode() : children(26, nullptr), isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for(char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for(char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                return false;
            }
            node = node->children[index];
        }
        return node != nullptr && node->isEndOfWord;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for(char c : prefix) {
            int index = c - 'a';
            if (!node->children[index]) {
                return false;
            }
            node = node->children[index];
        }
        return node != nullptr;
    }
};

Time Complexity

• Insert Operation: O(n)
  • n: The length of the word to be inserted.
  • Each character in the word is processed exactly once.
• Search Operation: O(n)
  • n: The length of the word to be searched.
  • Each character in the word is processed exactly once.
• startsWith Operation: O(n)
  • n: The length of the prefix.
  • Each character in the prefix is processed exactly once.

Given these complexities, the trie operations will be very efficient, particularly for string sets with a large number of common prefixes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?