Stream of Characters

🎯

Stream of Characters

hardTRIEAmazonGoogle

Imagine you're building a spell checker that listens to a continuous stream of characters and instantly tells you if the recent characters form any word from a dictionary.

💡 This problem requires efficiently checking if any suffix of a stream of characters matches a word from a given list. Beginners often struggle because naively checking all suffixes is expensive, and understanding how to use tries in reverse or suffix tries is non-trivial.

📋

Problem Statement

Design an algorithm that receives a stream of characters one by one and checks if any suffix of the characters seen so far forms a word from a given list of words. Implement the StreamChecker class: StreamChecker(words) initializes the data structure with the given list of words. boolean query(char letter) returns true if and only if for some k ≥ 1, the last k characters queried (including this letter just queried) form a word in the given list.

1 ≤ words.length ≤ 20001 ≤ words[i].length ≤ 200Words consist only of lowercase English letters.Queries can be up to 4 * 10^4 calls.

💡

Example

Input"words = [\"cd\",\"f\",\"kl\"], queries = ['a','b','c','d','e','f','g','h','i','j','k','l']"

Output[false,false,false,true,false,true,false,false,false,false,false,true]

After querying 'd', the suffix 'cd' matches a word. After querying 'f', 'f' matches. After querying 'l', 'kl' matches.

• Empty query stream → always false
• Words with single character → immediate match possible
• Queries with characters not in any word → always false
• Very long words with no matching suffix → false until full word matched

⚠️

Common Mistakes

Checking suffixes by scanning the entire stream every query

Leads to time limit exceeded on large inputs

✅ Use a trie with reversed words to check suffixes efficiently

Not reversing words when building the trie

Cannot efficiently check suffixes; traversal logic breaks

✅ Insert words reversed into the trie so suffixes become prefixes

Not limiting the stream buffer size

Memory usage grows unbounded and traversal slows down

✅ Keep only last max word length characters in the stream buffer

Returning false too early during trie traversal

Misses possible matches deeper in the trie

✅ Only return false when no child matches; continue traversal until end or match found

Using inefficient data structures for stream buffer

Appending and removing characters becomes costly

✅ Use efficient data structures like deque or StringBuilder

🧠

Brute Force (Check All Suffixes Each Query)

💡 This approach exists to establish a baseline and understand the problem deeply by trying all suffixes on every query, even though it's inefficient.

Intuition

On each query, append the letter to a stream and check every possible suffix against the list of words to see if any suffix matches a word.

Algorithm

1. Initialize an empty string to store the stream of queried characters.
2. For each query letter, append it to the stream.
3. For each suffix of the stream (from length 1 to full length), check if it matches any word in the list.
4. Return true if any suffix matches; otherwise, return false.

💡 The challenge is realizing that checking all suffixes is straightforward but costly, and this approach helps understand the problem's requirements.

</>

Code

class StreamChecker:
    def __init__(self, words):
        self.words = set(words)
        self.stream = ""

    def query(self, letter):
        self.stream += letter
        for i in range(len(self.stream)):
            if self.stream[i:] in self.words:
                return True
        return False

# Driver code
if __name__ == "__main__":
    sc = StreamChecker(["cd", "f", "kl"])
    queries = ['a','b','c','d','e','f','g','h','i','j','k','l']
    results = [sc.query(ch) for ch in queries]
    print(results)

Line Notes

self.words = set(words)Store words in a set for O(1) membership checks

self.stream = ""Keep track of all queried characters so far

self.stream += letterAppend the new letter to the stream

for i in range(len(self.stream))Check every possible suffix starting at i

if self.stream[i:] in self.wordsCheck if current suffix matches any word

return TrueReturn true immediately if a match is found

return FalseReturn false if no suffix matches

import java.util.*;

class StreamChecker {
    private Set<String> words;
    private StringBuilder stream;

    public StreamChecker(String[] words) {
        this.words = new HashSet<>();
        Collections.addAll(this.words, words);
        this.stream = new StringBuilder();
    }

    public boolean query(char letter) {
        stream.append(letter);
        for (int i = 0; i < stream.length(); i++) {
            if (words.contains(stream.substring(i))) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        StreamChecker sc = new StreamChecker(new String[]{"cd", "f", "kl"});
        char[] queries = {'a','b','c','d','e','f','g','h','i','j','k','l'};
        List<Boolean> results = new ArrayList<>();
        for (char ch : queries) {
            results.add(sc.query(ch));
        }
        System.out.println(results);
    }
}

Line Notes

this.words = new HashSet<>()Use a HashSet for O(1) word lookup

this.stream = new StringBuilder()Efficiently build the stream of characters

stream.append(letter)Add the new letter to the stream

for (int i = 0; i < stream.length(); i++)Check all suffixes starting at i

words.contains(stream.substring(i))Check if suffix is a word

return trueReturn true immediately if match found

return falseReturn false if no suffix matches

#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>

using namespace std;

class StreamChecker {
    unordered_set<string> words;
    string stream;
public:
    StreamChecker(vector<string>& wordsList) {
        for (auto& w : wordsList) words.insert(w);
        stream = "";
    }

    bool query(char letter) {
        stream.push_back(letter);
        for (size_t i = 0; i < stream.size(); ++i) {
            if (words.count(stream.substr(i))) return true;
        }
        return false;
    }
};

int main() {
    vector<string> words = {"cd", "f", "kl"};
    StreamChecker sc(words);
    vector<char> queries = {'a','b','c','d','e','f','g','h','i','j','k','l'};
    for (char ch : queries) {
        cout << (sc.query(ch) ? "true" : "false") << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

unordered_set<string> wordsStore words for O(1) lookup

string streamKeep track of all queried characters

stream.push_back(letter)Append new letter to stream

for (size_t i = 0; i < stream.size(); ++i)Check every suffix starting at i

words.count(stream.substr(i))Check if suffix is in words set

return trueReturn true if match found

return falseReturn false if no suffix matches

class StreamChecker {
    constructor(words) {
        this.words = new Set(words);
        this.stream = "";
    }

    query(letter) {
        this.stream += letter;
        for (let i = 0; i < this.stream.length; i++) {
            if (this.words.has(this.stream.substring(i))) {
                return true;
            }
        }
        return false;
    }
}

// Driver code
const sc = new StreamChecker(["cd", "f", "kl"]);
const queries = ['a','b','c','d','e','f','g','h','i','j','k','l'];
const results = queries.map(ch => sc.query(ch));
console.log(results);

Line Notes

this.words = new Set(words)Store words for quick membership checks

this.stream = ""Keep track of all queried characters

this.stream += letterAppend new letter to the stream

for (let i = 0; i < this.stream.length; i++)Check all suffixes starting at i

this.words.has(this.stream.substring(i))Check if suffix is a word

return trueReturn true immediately if match found

return falseReturn false if no suffix matches

⏱

Complexity

TimeO(Q * W * L) where Q is number of queries, W is number of words, L is max word length

SpaceO(W * L) to store words and O(Q) for the stream

Each query checks all suffixes against all words, leading to a large number of substring comparisons.

💡 For 10,000 queries and 2,000 words of length 200, this approach is impractical as it could do billions of checks.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Trie with Reversed Words + Stream Buffer

💡 This approach improves efficiency by building a trie of reversed words and checking suffixes by traversing the trie backwards through the stream.

Intuition

Store all words reversed in a trie. On each query, add the letter to a buffer and traverse the trie from the newest letter backwards to check if any suffix matches a word.

Algorithm

1. Build a trie where each word is inserted in reversed order.
2. Maintain a buffer of queried characters.
3. On each query, append the letter to the buffer.
4. Traverse the trie starting from the last character in the buffer backwards, following trie edges.
5. If at any point a node marks the end of a word, return true.
6. If traversal ends without a match, return false.

💡 The key insight is reversing words so suffix checks become prefix checks in the trie, enabling efficient traversal.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

# Driver code
if __name__ == "__main__":
    sc = StreamChecker(["cd", "f", "kl"])
    queries = ['a','b','c','d','e','f','g','h','i','j','k','l']
    results = [sc.query(ch) for ch in queries]
    print(results)

Line Notes

self.root = TrieNode()Initialize root of trie

self.stream = []Store queried characters in a list for efficient append

for ch in reversed(word)Insert words reversed to enable suffix checking

node.is_word = TrueMark end of a word in trie

self.stream.append(letter)Add new letter to stream buffer

for ch in reversed(self.stream)Traverse stream backwards to check suffixes

if ch not in node.childrenStop traversal if no matching edge

if node.is_wordReturn true if a suffix matches a word

import java.util.*;

class StreamChecker {
    private static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isWord = false;
    }

    private TrieNode root;
    private StringBuilder stream;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        stream = new StringBuilder();
        for (String word : words) {
            TrieNode node = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                char ch = word.charAt(i);
                node.children.putIfAbsent(ch, new TrieNode());
                node = node.children.get(ch);
            }
            node.isWord = true;
        }
    }

    public boolean query(char letter) {
        stream.append(letter);
        TrieNode node = root;
        for (int i = stream.length() - 1; i >= 0; i--) {
            char ch = stream.charAt(i);
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
            if (node.isWord) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        StreamChecker sc = new StreamChecker(new String[]{"cd", "f", "kl"});
        char[] queries = {'a','b','c','d','e','f','g','h','i','j','k','l'};
        List<Boolean> results = new ArrayList<>();
        for (char ch : queries) {
            results.add(sc.query(ch));
        }
        System.out.println(results);
    }
}

Line Notes

root = new TrieNode()Initialize trie root

stream = new StringBuilder()Store queried characters efficiently

for (int i = word.length() - 1; i >= 0; i--)Insert words reversed into trie

node.children.putIfAbsent(ch, new TrieNode())Create child node if missing

node.isWord = trueMark end of word

stream.append(letter)Add new letter to stream

for (int i = stream.length() - 1; i >= 0; i--)Traverse stream backwards

if (!node.children.containsKey(ch)) return falseStop if no matching child

if (node.isWord) return trueReturn true if suffix matches

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isWord = false;
};

class StreamChecker {
    TrieNode* root;
    vector<char> stream;
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for (auto& word : words) {
            TrieNode* node = root;
            for (int i = (int)word.size() - 1; i >= 0; --i) {
                char ch = word[i];
                if (!node->children.count(ch))
                    node->children[ch] = new TrieNode();
                node = node->children[ch];
            }
            node->isWord = true;
        }
    }

    bool query(char letter) {
        stream.push_back(letter);
        TrieNode* node = root;
        for (int i = (int)stream.size() - 1; i >= 0; --i) {
            char ch = stream[i];
            if (!node->children.count(ch)) return false;
            node = node->children[ch];
            if (node->isWord) return true;
        }
        return false;
    }
};

int main() {
    vector<string> words = {"cd", "f", "kl"};
    StreamChecker sc(words);
    vector<char> queries = {'a','b','c','d','e','f','g','h','i','j','k','l'};
    for (char ch : queries) {
        cout << (sc.query(ch) ? "true" : "false") << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

root = new TrieNode()Create root node for trie

for (int i = (int)word.size() - 1; i >= 0; --i)Insert words reversed

if (!node->children.count(ch))Create child node if missing

node->isWord = trueMark end of word

stream.push_back(letter)Add letter to stream buffer

for (int i = (int)stream.size() - 1; i >= 0; --i)Traverse stream backwards

if (!node->children.count(ch)) return falseStop if no matching child

if (node->isWord) return trueReturn true if suffix matches

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isWord = false;
    }
}

class StreamChecker {
    constructor(words) {
        this.root = new TrieNode();
        this.stream = [];
        for (const word of words) {
            let node = this.root;
            for (let i = word.length - 1; i >= 0; i--) {
                const ch = word[i];
                if (!node.children.has(ch)) {
                    node.children.set(ch, new TrieNode());
                }
                node = node.children.get(ch);
            }
            node.isWord = true;
        }
    }

    query(letter) {
        this.stream.push(letter);
        let node = this.root;
        for (let i = this.stream.length - 1; i >= 0; i--) {
            const ch = this.stream[i];
            if (!node.children.has(ch)) return false;
            node = node.children.get(ch);
            if (node.isWord) return true;
        }
        return false;
    }
}

// Driver code
const sc = new StreamChecker(["cd", "f", "kl"]);
const queries = ['a','b','c','d','e','f','g','h','i','j','k','l'];
const results = queries.map(ch => sc.query(ch));
console.log(results);

Line Notes

this.root = new TrieNode()Initialize trie root node

this.stream = []Store queried characters in an array

for (let i = word.length - 1; i >= 0; i--)Insert words reversed into trie

node.children.set(ch, new TrieNode())Create child node if missing

node.isWord = trueMark end of word

this.stream.push(letter)Add new letter to stream

for (let i = this.stream.length - 1; i >= 0; i--)Traverse stream backwards

if (!node.children.has(ch)) return falseStop if no matching child

if (node.isWord) return trueReturn true if suffix matches

⏱

Complexity

TimeO(Q * L) where Q is number of queries and L is max word length

SpaceO(W * L) for trie storage and O(Q) for stream buffer

Each query traverses at most L trie nodes, much faster than brute force checking all suffixes.

💡 For 40,000 queries and max word length 200, this approach does about 8 million operations, which is feasible.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs, demonstrating mastery of tries and suffix checking.

🧠

Trie with Stream Buffer Limited to Max Word Length

💡 This approach further optimizes memory by limiting the stream buffer size to the longest word length, avoiding unnecessary traversal of irrelevant suffixes.

Intuition

Since no suffix longer than the longest word can match, keep only the last max word length characters in the buffer to reduce traversal time and memory.

Algorithm

1. Find the maximum length of words in the list.
2. Build a trie of reversed words as before.
3. Maintain a stream buffer that stores only the last max word length characters.
4. On each query, append the letter and remove oldest if buffer exceeds max length.
5. Traverse the trie backwards through the buffer to check for suffix matches.
6. Return true if a word is matched; otherwise, false.

💡 Limiting the buffer size reduces unnecessary checks and memory usage without affecting correctness.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

# Driver code
if __name__ == "__main__":
    sc = StreamChecker(["cd", "f", "kl"])
    queries = ['a','b','c','d','e','f','g','h','i','j','k','l']
    results = [sc.query(ch) for ch in queries]
    print(results)

Line Notes

self.max_len = max(len(w) for w in words)Calculate max word length to limit buffer

if len(self.stream) > self.max_lenRemove oldest character if buffer too long

self.stream.pop(0)Maintain buffer size within max length

for ch in reversed(self.stream)Traverse only relevant suffixes

node.is_word = TrueMark end of word in trie

return TrueReturn true if suffix matches

return FalseReturn false if no match

import java.util.*;

class StreamChecker {
    private static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isWord = false;
    }

    private TrieNode root;
    private LinkedList<Character> stream;
    private int maxLen;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        stream = new LinkedList<>();
        maxLen = 0;
        for (String word : words) {
            maxLen = Math.max(maxLen, word.length());
            TrieNode node = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                char ch = word.charAt(i);
                node.children.putIfAbsent(ch, new TrieNode());
                node = node.children.get(ch);
            }
            node.isWord = true;
        }
    }

    public boolean query(char letter) {
        stream.addLast(letter);
        if (stream.size() > maxLen) stream.removeFirst();
        TrieNode node = root;
        Iterator<Character> it = stream.descendingIterator();
        while (it.hasNext()) {
            char ch = it.next();
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
            if (node.isWord) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        StreamChecker sc = new StreamChecker(new String[]{"cd", "f", "kl"});
        char[] queries = {'a','b','c','d','e','f','g','h','i','j','k','l'};
        List<Boolean> results = new ArrayList<>();
        for (char ch : queries) {
            results.add(sc.query(ch));
        }
        System.out.println(results);
    }
}

Line Notes

maxLen = 0Initialize max length variable

maxLen = Math.max(maxLen, word.length())Update max length while inserting words

stream = new LinkedList<>()Use linked list for efficient removals

if (stream.size() > maxLen) stream.removeFirst()Remove oldest character to limit buffer size

Iterator<Character> it = stream.descendingIterator()Traverse stream backwards

if (!node.children.containsKey(ch)) return falseStop if no matching child

if (node.isWord) return trueReturn true if suffix matches

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <deque>

using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isWord = false;
};

class StreamChecker {
    TrieNode* root;
    deque<char> stream;
    int maxLen;
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        maxLen = 0;
        for (auto& word : words) {
            maxLen = max(maxLen, (int)word.size());
            TrieNode* node = root;
            for (int i = (int)word.size() - 1; i >= 0; --i) {
                char ch = word[i];
                if (!node->children.count(ch))
                    node->children[ch] = new TrieNode();
                node = node->children[ch];
            }
            node->isWord = true;
        }
    }

    bool query(char letter) {
        stream.push_back(letter);
        if ((int)stream.size() > maxLen) stream.pop_front();
        TrieNode* node = root;
        for (auto it = stream.rbegin(); it != stream.rend(); ++it) {
            char ch = *it;
            if (!node->children.count(ch)) return false;
            node = node->children[ch];
            if (node->isWord) return true;
        }
        return false;
    }
};

int main() {
    vector<string> words = {"cd", "f", "kl"};
    StreamChecker sc(words);
    vector<char> queries = {'a','b','c','d','e','f','g','h','i','j','k','l'};
    for (char ch : queries) {
        cout << (sc.query(ch) ? "true" : "false") << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

maxLen = 0Initialize max word length

maxLen = max(maxLen, (int)word.size())Update max length while inserting words

deque<char> streamUse deque to efficiently pop front

if ((int)stream.size() > maxLen) stream.pop_front()Limit buffer size to max length

for (auto it = stream.rbegin(); it != stream.rend(); ++it)Traverse stream backwards

if (!node->children.count(ch)) return falseStop if no matching child

if (node->isWord) return trueReturn true if suffix matches

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isWord = false;
    }
}

class StreamChecker {
    constructor(words) {
        this.root = new TrieNode();
        this.stream = [];
        this.maxLen = 0;
        for (const word of words) {
            this.maxLen = Math.max(this.maxLen, word.length);
            let node = this.root;
            for (let i = word.length - 1; i >= 0; i--) {
                const ch = word[i];
                if (!node.children.has(ch)) {
                    node.children.set(ch, new TrieNode());
                }
                node = node.children.get(ch);
            }
            node.isWord = true;
        }
    }

    query(letter) {
        this.stream.push(letter);
        if (this.stream.length > this.maxLen) {
            this.stream.shift();
        }
        let node = this.root;
        for (let i = this.stream.length - 1; i >= 0; i--) {
            const ch = this.stream[i];
            if (!node.children.has(ch)) return false;
            node = node.children.get(ch);
            if (node.isWord) return true;
        }
        return false;
    }
}

// Driver code
const sc = new StreamChecker(["cd", "f", "kl"]);
const queries = ['a','b','c','d','e','f','g','h','i','j','k','l'];
const results = queries.map(ch => sc.query(ch));
console.log(results);

Line Notes

this.maxLen = 0Initialize max word length

this.maxLen = Math.max(this.maxLen, word.length)Update max length while inserting words

this.stream = []Store queried characters

if (this.stream.length > this.maxLen) this.stream.shift()Remove oldest character to limit buffer

for (let i = this.stream.length - 1; i >= 0; i--)Traverse stream backwards

if (!node.children.has(ch)) return falseStop if no matching child

if (node.isWord) return trueReturn true if suffix matches

⏱

Complexity

TimeO(Q * L) where Q is queries and L is max word length

SpaceO(W * L) for trie and O(L) for stream buffer

Limiting buffer size reduces memory and traversal length, improving performance slightly.

💡 This approach is the most practical and efficient for large inputs, balancing speed and memory.

Interview Verdict: Accepted

This is the best practical solution, showing mastery of trie optimization and stream handling.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the optimized trie with reversed words and limited buffer is best; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(Q * W * L)	O(W * L + Q)	No	N/A	Mention only - never code
2. Trie with Reversed Words	O(Q * L)	O(W * L + Q)	No	N/A	Code this for efficient solution
3. Trie with Stream Buffer Limited to Max Word Length	O(Q * L)	O(W * L + L)	No	N/A	Best practical approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Present brute force approach to show understanding.Step 3: Explain inefficiency and introduce trie with reversed words.Step 4: Optimize by limiting stream buffer size.Step 5: Code the optimized approach and test edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of tries, suffix checking, optimization techniques, and ability to handle streaming data efficiently.

Common Follow-ups

• How to handle uppercase letters or other character sets → Use case normalization or extend trie nodes.
• Can you optimize space further → Use a fixed-size circular buffer for stream.
• What if words are extremely long → Consider suffix automaton or Aho-Corasick algorithm.
• How to handle deletions in the stream → More complex data structures needed, possibly suffix trees.

💡 These follow-ups test your ability to adapt the solution to real-world constraints and advanced data structures.

🔍

Pattern Recognition

When to Use

1) Need to check if suffixes of a stream match words; 2) Words are known upfront; 3) Queries come one character at a time; 4) Efficient suffix checking required.

Signature Phrases

stream of characterslast k charactersends with wordquery stream

NOT This Pattern When

Problems that require substring matching anywhere (not suffix) or offline queries are different patterns.

Similar Problems

Implement Trie (Prefix Tree) - foundational trie constructionDesign Add and Search Words Data Structure - trie with wildcardsWord Search II - trie + backtracking for word search

Practice

1. Consider the following code snippet for the search method of a WordDictionary implemented with a trie. After adding the words "bad", "dad", and "mad", what is the return value of search(".ad")?

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        stack = [(0, self.root)]
        while stack:
            index, node = stack.pop()
            if index == len(word):
                if node.is_end:
                    return True
                continue
            ch = word[index]
            if ch == '.':
                for child in node.children.values():
                    stack.append((index + 1, child))
            else:
                if ch in node.children:
                    stack.append((index + 1, node.children[ch]))
        return False

easy

A. Depends on the order of insertion

B. False

C. Raises an exception

D. True

Solution

1. Step 1: Trace search(".ad") with words added

   Words "bad", "dad", "mad" are added. The search starts at root with index 0 and '.' wildcard matches all children 'b', 'd', 'm'.

2. Step 2: Explore all branches for 'a' and 'd'

   For each child, next character 'a' is matched, then 'd'. All three words match ".ad" pattern, so search returns True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Wildcard '.' matches all first letters; all three words match pattern [OK]

Hint: Wildcard '.' matches any child node [OK]

Common Mistakes:

• Assuming '.' matches only one fixed letter
• Forgetting to check is_end at word end
• Thinking search depends on insertion order

2. The following code attempts to count pairs with XOR less than a limit using a bitwise trie. Identify the line that contains a subtle bug that causes incorrect counts on some inputs.

medium

A. Line where node.count is incremented during insert

B. Line where the trie is not reset between queries causing accumulation

C. Line where result accumulates query(num, limit) before insert

D. Line where node is updated to node.children[bit] during insert

Solution

1. Step 1: Understand trie usage in counting pairs

   The trie accumulates counts of inserted numbers to query how many have XOR less than limit with current number.

2. Step 2: Identify the bug

   The code does not reset or clear the trie between different calls or test cases, causing counts to accumulate incorrectly if reused, leading to wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Not resetting trie causes stale counts to affect results [OK]

Hint: Trie must be fresh or cleared per independent query [OK]

Common Mistakes:

• Not resetting trie between test cases
• Incrementing count incorrectly
• Wrong bit traversal order

3. What is the time complexity of the sum(prefix) operation in the optimal MapSum implementation using a trie with array children, assuming average key length is k and n keys inserted?

medium

A. O(n * k) because we must scan all keys to sum prefix matches.

B. O(k) because we traverse the trie nodes corresponding to the prefix length.

C. O(k * 26) because we check all children at each prefix node.

D. O(log n) because trie nodes are balanced like a BST.

Solution

1. Step 1: Identify sum operation steps

   Sum traverses trie nodes along prefix characters only, no scanning of all keys.

2. Step 2: Analyze traversal cost

   Each character leads to one child node via array index, so traversal is O(k) where k is prefix length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum is O(k) due to direct trie traversal [INCORRECT]

Hint: Sum only traverses prefix length nodes, not all keys [INCORRECT]

Common Mistakes:

• Confusing sum with brute force scanning
• Thinking all children checked at each node
• Assuming trie is balanced BST

4. Consider the following buggy code snippet for the trie-based solution. Which line contains the subtle bug that causes incorrect replacements?

medium

A. Line where node.is_end is set to True in insert method

B. Line where children dictionary is checked for char in search_shortest_prefix

C. Line where prefix is returned without checking node.is_end in search_shortest_prefix

D. Line where sentence is split into words in replaceWords function

Solution

1. Step 1: Identify the bug in search_shortest_prefix

   The function returns prefix after traversing all characters without checking if the current node marks the end of a root word.

2. Step 2: Consequence of missing is_end check

   This causes longer prefixes to replace shorter roots, violating the shortest prefix requirement.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding is_end check inside loop fixes the bug [OK]

Hint: Always check is_end during prefix search [OK]

Common Mistakes:

• Returning prefix without is_end check
• Not stopping early at shortest prefix

5. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words