algoadvance

Leetcode 208. Implement Trie (Prefix Tree)

Problem Statement

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

• 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.

Clarifying Questions

1. Q: Can we assume all inputs are lowercase English letters? A: Yes, all inputs are guaranteed to be lowercase English letters (a-z).

2. Q: What is the maximum length of word or prefix? A: You can assume that the maximum length of word or prefix is 2000.

3. Q: Can we have duplicate insertions of the same word? A: Yes, duplicate insertions are allowed, but they should be ignored in terms of storage.

Strategy

We’ll use a class TrieNode for the nodes of the trie. Each node contains:

• An array of TrieNode references for each character a-z.
• A boolean isEnd to mark the end of a word.

We then implement the Trie class using these nodes:

• The insert method will iterate over the characters of the word and insert nodes accordingly.
• The search method will traverse the trie based on the characters of the word and check isEnd.
• The startsWith method will traverse the trie and return true if all characters of the prefix are found.

Code

class TrieNode {
    public TrieNode[] children;
    public boolean isEnd;
    
    public TrieNode() {
        // Initialize children for 26 lowercase English letters
        children = new TrieNode[26];
        isEnd = false;
    }
}

public class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

Time Complexity

• Insert: O(m) where m is the length of the word. We need to traverse each character of the word.
• Search: O(m) where m is the length of the word. We need to traverse each character to find a match.
• StartsWith: O(m) where m is the length of the prefix. We need to traverse each character to check for the prefix.

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?