Design Add and Search Words Data Structure

🎯

Design Add and Search Words Data Structure

mediumTRIEFacebookAmazonGoogle

Imagine building a spell checker that not only stores words but also supports searching with wildcards, making it easy to find words even if you only know part of them.

💡 This problem introduces the trie data structure with a twist: searching with a wildcard character '.' that can match any letter. Beginners often struggle because they must combine trie traversal with backtracking to handle wildcards, which is more complex than straightforward prefix matching.

📋

Problem Statement

Design a data structure that supports adding new words and searching if a string matches any previously added string. The search string may contain the '.' character which can match any letter. Implement the WordDictionary class: - WordDictionary() Initializes the object. - void addWord(word) Adds word to the data structure. - bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain '.' characters where '.' can match any letter.

1 ≤ word.length ≤ 25word in addWord consists of lowercase English lettersword in search consists of lowercase English letters or '.'At most 3 * 10^4 calls will be made to addWord and search

💡

Example

Input"addWord(\"bad\"), addWord(\"dad\"), addWord(\"mad\"), search(\"pad\"), search(\"bad\"), search(\".ad\"), search(\"b..\")"

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

After adding 'bad', 'dad', and 'mad', searching 'pad' returns false as it was not added. Searching 'bad' returns true. Searching '.ad' matches any word ending with 'ad', so returns true. Searching 'b..' matches any word starting with 'b' and two letters after, so returns true.

• searching an empty string → false (no empty words added)
• adding duplicate words → should not affect search results
• searching with all '.' characters → matches any word of that length
• searching for a word longer than any added word → false

⚠️

Common Mistakes

Not handling '.' wildcard correctly in search

Search returns false negatives or crashes

✅ Implement DFS to explore all children when '.' is encountered

Not marking end of word in trie nodes

Search may return false for words that were added

✅ Set is_end or isEnd flag at last node of added word

Using recursion without base case for search

Stack overflow or infinite recursion

✅ Add base case when index reaches word length

Ignoring word length mismatch in brute force

Incorrect matches or wasted computation

✅ Check length equality before character-by-character match

Not handling empty input or empty trie

Null pointer exceptions or incorrect results

✅ Initialize root node and handle empty search gracefully

🧠

Brute Force (Store Words and Linear Search with Backtracking)

💡 This approach exists to build intuition by treating the problem as a simple list search with backtracking for wildcards, without any optimization. It helps beginners understand the complexity of wildcard matching before moving to tries.

Intuition

Store all words in a list. For search, iterate over all words and check if each matches the search pattern using recursion to handle '.' wildcards.

Algorithm

1. Initialize an empty list to store words.
2. To add a word, append it to the list.
3. To search, iterate over all stored words.
4. For each word, recursively check if it matches the search pattern, handling '.' as a wildcard.

💡 The main challenge is implementing the recursive matching that handles '.' correctly, which is the core of the problem.

</>

Code

class WordDictionary:
    def __init__(self):
        self.words = []

    def addWord(self, word: str) -> None:
        self.words.append(word)

    def search(self, word: str) -> bool:
        def match(w, pattern):
            if len(w) != len(pattern):
                return False
            for i in range(len(w)):
                if pattern[i] != '.' and pattern[i] != w[i]:
                    return False
            return True

        for w in self.words:
            if match(w, word):
                return True
        return False

# Driver code
wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))  # False
print(wd.search("bad"))  # True
print(wd.search(".ad"))  # True
print(wd.search("b.."))  # True

Line Notes

self.words = []Initialize storage for all added words in a list

self.words.append(word)Add new words by appending to the list

if len(w) != len(pattern)Quickly reject words of different length

if pattern[i] != '.' and pattern[i] != w[i]Check character match or wildcard '.'

for w in self.wordsIterate over all stored words to find a match

return TrueReturn true immediately when a matching word is found

import java.util.*;

class WordDictionary {
    private List<String> words;

    public WordDictionary() {
        words = new ArrayList<>();
    }

    public void addWord(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        for (String w : words) {
            if (match(w, word)) return true;
        }
        return false;
    }

    private boolean match(String w, String pattern) {
        if (w.length() != pattern.length()) return false;
        for (int i = 0; i < w.length(); i++) {
            if (pattern.charAt(i) != '.' && pattern.charAt(i) != w.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    // Main method for testing
    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();
        wd.addWord("bad");
        wd.addWord("dad");
        wd.addWord("mad");
        System.out.println(wd.search("pad"));  // false
        System.out.println(wd.search("bad"));  // true
        System.out.println(wd.search(".ad"));  // true
        System.out.println(wd.search("b.."));  // true
    }
}

Line Notes

words = new ArrayList<>()Initialize list to store words

words.add(word)Add word to the list

if (w.length() != pattern.length())Reject words with different length quickly

if (pattern.charAt(i) != '.' && pattern.charAt(i) != w.charAt(i))Check character or wildcard match

for (String w : words)Iterate over all words to find a match

return trueReturn true immediately when a matching word is found

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class WordDictionary {
    vector<string> words;
public:
    WordDictionary() {}

    void addWord(string word) {
        words.push_back(word);
    }

    bool match(const string& w, const string& pattern) {
        if (w.size() != pattern.size()) return false;
        for (int i = 0; i < (int)w.size(); i++) {
            if (pattern[i] != '.' && pattern[i] != w[i]) return false;
        }
        return true;
    }

    bool search(string word) {
        for (auto& w : words) {
            if (match(w, word)) return true;
        }
        return false;
    }
};

int main() {
    WordDictionary wd;
    wd.addWord("bad");
    wd.addWord("dad");
    wd.addWord("mad");
    cout << boolalpha << wd.search("pad") << "\n";  // false
    cout << boolalpha << wd.search("bad") << "\n";  // true
    cout << boolalpha << wd.search(".ad") << "\n";  // true
    cout << boolalpha << wd.search("b..") << "\n";  // true
    return 0;
}

Line Notes

vector<string> words;Store all added words in a vector

words.push_back(word);Add new words to the vector

if (w.size() != pattern.size())Quick length check to skip impossible matches

if (pattern[i] != '.' && pattern[i] != w[i])Check each character or wildcard match

for (auto& w : words)Check all words for a matching pattern

return trueReturn true immediately when a matching word is found

class WordDictionary {
    constructor() {
        this.words = [];
    }

    addWord(word) {
        this.words.push(word);
    }

    search(word) {
        const match = (w, pattern) => {
            if (w.length !== pattern.length) return false;
            for (let i = 0; i < w.length; i++) {
                if (pattern[i] !== '.' && pattern[i] !== w[i]) return false;
            }
            return true;
        };

        for (const w of this.words) {
            if (match(w, word)) return true;
        }
        return false;
    }
}

// Test
const wd = new WordDictionary();
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
console.log(wd.search("pad"));  // false
console.log(wd.search("bad"));  // true
console.log(wd.search(".ad"));  // true
console.log(wd.search("b.."));  // true

Line Notes

this.words = []Initialize array to store words

this.words.push(word)Add word to storage

if (w.length !== pattern.length)Skip words of different length

if (pattern[i] !== '.' && pattern[i] !== w[i])Check character or wildcard match

for (const w of this.words)Iterate all words to find a match

return trueReturn true immediately when a matching word is found

⏱

Complexity

TimeO(N * L) per search, where N is number of words and L is word length

SpaceO(N * L) to store all words

Each search checks all stored words, comparing character by character, leading to linear time in number of words times word length.

💡 If you add 10,000 words each of length 10, searching could take up to 100,000 character comparisons, which is slow for large inputs.

Interview Verdict: TLE for large inputs, but useful to understand problem basics

This approach is too slow for big data but helps grasp wildcard matching before optimizing with tries.

🧠

Trie with DFS Backtracking for Wildcard Search

💡 This approach uses a trie to store words efficiently and applies DFS backtracking to handle '.' wildcards during search. It introduces the core data structure and recursion pattern needed for optimal performance.

Intuition

Build a trie where each node represents a character. For search, traverse the trie matching characters. When encountering '.', recursively search all child nodes.

Algorithm

1. Create a trie node class with children and end-of-word flag.
2. Add words by inserting characters into the trie nodes.
3. Search by traversing trie nodes matching characters.
4. If '.' is encountered, recursively search all children nodes.

💡 The key insight is combining trie traversal with recursive branching on '.' wildcards.

</>

Code

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:
        def dfs(j, node):
            if j == len(word):
                return node.is_end
            ch = word[j]
            if ch == '.':
                for child in node.children.values():
                    if dfs(j + 1, child):
                        return True
                return False
            else:
                if ch not in node.children:
                    return False
                return dfs(j + 1, node.children[ch])

        return dfs(0, self.root)

# Driver code
wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))  # False
print(wd.search("bad"))  # True
print(wd.search(".ad"))  # True
print(wd.search("b.."))  # True

Line Notes

self.children = {}Use dictionary to store child nodes for each character

if ch not in node.childrenCreate new trie node if character path doesn't exist

node.is_end = TrueMark end of a valid word

if ch == '.'Wildcard triggers DFS over all children

return dfs(j + 1, node.children[ch])Continue traversal for matching character

import java.util.*;

class WordDictionary {
    private class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEnd = false;
    }

    private TrieNode root;

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

    public void addWord(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int index, TrieNode node) {
        if (index == word.length()) return node.isEnd;
        char ch = word.charAt(index);
        if (ch == '.') {
            for (TrieNode child : node.children.values()) {
                if (dfs(word, index + 1, child)) return true;
            }
            return false;
        } else {
            if (!node.children.containsKey(ch)) return false;
            return dfs(word, index + 1, node.children.get(ch));
        }
    }

    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();
        wd.addWord("bad");
        wd.addWord("dad");
        wd.addWord("mad");
        System.out.println(wd.search("pad"));  // false
        System.out.println(wd.search("bad"));  // true
        System.out.println(wd.search(".ad"));  // true
        System.out.println(wd.search("b.."));  // true
    }
}

Line Notes

Map<Character, TrieNode> children = new HashMap<>()Store children nodes in a map for quick lookup

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

node.isEnd = trueMark node as end of a word

if (ch == '.')Wildcard triggers DFS over all children

return dfs(word, index + 1, node.children.get(ch))Traverse matching child node

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

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

    void addWord(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool dfs(string& word, int index, TrieNode* node) {
        if (index == (int)word.size()) return node->isEnd;
        char ch = word[index];
        if (ch == '.') {
            for (auto& p : node->children) {
                if (dfs(word, index + 1, p.second)) return true;
            }
            return false;
        } else {
            if (node->children.find(ch) == node->children.end()) return false;
            return dfs(word, index + 1, node->children[ch]);
        }
    }

    bool search(string word) {
        return dfs(word, 0, root);
    }
};

int main() {
    WordDictionary wd;
    wd.addWord("bad");
    wd.addWord("dad");
    wd.addWord("mad");
    cout << boolalpha << wd.search("pad") << "\n";  // false
    cout << boolalpha << wd.search("bad") << "\n";  // true
    cout << boolalpha << wd.search(".ad") << "\n";  // true
    cout << boolalpha << wd.search("b..") << "\n";  // true
    return 0;
}

Line Notes

unordered_map<char, TrieNode*> children;Map children characters to trie nodes for fast access

if (node->children.find(ch) == node->children.end())Create new node if path missing

node->isEnd = true;Mark end of word

if (ch == '.')Wildcard triggers DFS over all children

return dfs(word, index + 1, node->children[ch]);Traverse matching child node

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

class WordDictionary {
    constructor() {
        this.root = new TrieNode();
    }

    addWord(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    search(word) {
        const dfs = (index, node) => {
            if (index === word.length) return node.isEnd;
            const ch = word[index];
            if (ch === '.') {
                for (const child of node.children.values()) {
                    if (dfs(index + 1, child)) return true;
                }
                return false;
            } else {
                if (!node.children.has(ch)) return false;
                return dfs(index + 1, node.children.get(ch));
            }
        };
        return dfs(0, this.root);
    }
}

// Test
const wd = new WordDictionary();
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
console.log(wd.search("pad"));  // false
console.log(wd.search("bad"));  // true
console.log(wd.search(".ad"));  // true
console.log(wd.search("b.."));  // true

Line Notes

this.children = new Map()Use Map to store children nodes for efficient lookup

if (!node.children.has(ch))Create new child node if missing

node.isEnd = trueMark node as end of a word

if (ch === '.')Wildcard triggers DFS over all children

return dfs(index + 1, node.children.get(ch))Traverse child node matching character

⏱

Complexity

TimeO(L) for addWord, O(26^m) worst-case for search with m wildcards

SpaceO(N * L) for trie storage

Adding words is linear in word length. Searching is linear unless wildcards cause branching, which can be exponential in worst case but usually efficient.

💡 For typical inputs, search is fast, but many '.' characters increase branching exponentially.

Interview Verdict: Accepted and efficient for most cases

This is the standard and optimal approach for this problem in interviews.

🧠

Trie with Iterative Search Using Stack for Wildcard Handling

💡 This approach replaces recursion with an explicit stack to perform DFS iteratively, which can avoid stack overflow and is preferred in some interview scenarios.

Intuition

Use a trie to store words. For search, use a stack to simulate DFS. When '.' is encountered, push all children nodes onto the stack to explore.

Algorithm

1. Build a trie as usual for addWord.
2. For search, initialize a stack with the root node and index 0.
3. While stack not empty, pop a node and index.
4. If index equals word length and node is end, return true.
5. If current character is '.', push all children with next index.
6. Else push child matching character if exists.
7. Return false if no match found.

💡 This approach simulates recursion with a stack, making control flow explicit.

</>

Code

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

# Driver code
wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))  # False
print(wd.search("bad"))  # True
print(wd.search(".ad"))  # True
print(wd.search("b.."))  # True

Line Notes

stack = [(0, self.root)]Initialize stack with starting index and root node

while stack:Iterate until all paths explored

if index == len(word)Check if reached end of search word

if ch == '.':Wildcard triggers pushing all children to stack

stack.append((index + 1, node.children[ch]))Push next node for matching character

import java.util.*;

class WordDictionary {
    private class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEnd = false;
    }

    private TrieNode root;

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

    public void addWord(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Deque<Pair> stack = new ArrayDeque<>();
        stack.push(new Pair(0, root));
        while (!stack.isEmpty()) {
            Pair p = stack.pop();
            int index = p.index;
            TrieNode node = p.node;
            if (index == word.length()) {
                if (node.isEnd) return true;
                continue;
            }
            char ch = word.charAt(index);
            if (ch == '.') {
                for (TrieNode child : node.children.values()) {
                    stack.push(new Pair(index + 1, child));
                }
            } else {
                if (node.children.containsKey(ch)) {
                    stack.push(new Pair(index + 1, node.children.get(ch)));
                }
            }
        }
        return false;
    }

    private class Pair {
        int index;
        TrieNode node;
        Pair(int i, TrieNode n) { index = i; node = n; }
    }

    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();
        wd.addWord("bad");
        wd.addWord("dad");
        wd.addWord("mad");
        System.out.println(wd.search("pad"));  // false
        System.out.println(wd.search("bad"));  // true
        System.out.println(wd.search(".ad"));  // true
        System.out.println(wd.search("b.."));  // true
    }
}

Line Notes

Deque<Pair> stack = new ArrayDeque<>()Use stack to simulate DFS iteratively

stack.push(new Pair(0, root))Start from root and index 0

if (index == word.length())Check if search word fully matched

if (ch == '.')Wildcard triggers pushing all children

stack.push(new Pair(index + 1, node.children.get(ch)))Push next node for matching character

#include <iostream>
#include <unordered_map>
#include <stack>
#include <string>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

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

    void addWord(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        stack<pair<int, TrieNode*>> stk;
        stk.push({0, root});
        while (!stk.empty()) {
            auto [index, node] = stk.top();
            stk.pop();
            if (index == (int)word.size()) {
                if (node->isEnd) return true;
                continue;
            }
            char ch = word[index];
            if (ch == '.') {
                for (auto& p : node->children) {
                    stk.push({index + 1, p.second});
                }
            } else {
                if (node->children.find(ch) != node->children.end()) {
                    stk.push({index + 1, node->children[ch]});
                }
            }
        }
        return false;
    }
};

int main() {
    WordDictionary wd;
    wd.addWord("bad");
    wd.addWord("dad");
    wd.addWord("mad");
    cout << boolalpha << wd.search("pad") << "\n";  // false
    cout << boolalpha << wd.search("bad") << "\n";  // true
    cout << boolalpha << wd.search(".ad") << "\n";  // true
    cout << boolalpha << wd.search("b..") << "\n";  // true
    return 0;
}

Line Notes

stack<pair<int, TrieNode*>> stk;Use stack to hold pairs of index and trie node

stk.push({0, root});Start search from root and index 0

if (index == (int)word.size())Check if full word matched

if (ch == '.')Wildcard triggers pushing all children

stk.push({index + 1, node->children[ch]});Push next node for matching character

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

class WordDictionary {
    constructor() {
        this.root = new TrieNode();
    }

    addWord(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    search(word) {
        const stack = [[0, this.root]];
        while (stack.length > 0) {
            const [index, node] = stack.pop();
            if (index === word.length) {
                if (node.isEnd) return true;
                continue;
            }
            const ch = word[index];
            if (ch === '.') {
                for (const child of node.children.values()) {
                    stack.push([index + 1, child]);
                }
            } else {
                if (node.children.has(ch)) {
                    stack.push([index + 1, node.children.get(ch)]);
                }
            }
        }
        return false;
    }
}

// Test
const wd = new WordDictionary();
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
console.log(wd.search("pad"));  // false
console.log(wd.search("bad"));  // true
console.log(wd.search(".ad"));  // true
console.log(wd.search("b.."));  // true

Line Notes

const stack = [[0, this.root]];Initialize stack with starting index and root node

while (stack.length > 0)Loop until all search paths are explored

if (index === word.length)Check if full word matched

if (ch === '.')Wildcard triggers pushing all children

stack.push([index + 1, node.children.get(ch)])Push next node for matching character

⏱

Complexity

TimeO(L) for addWord, O(26^m) worst-case for search with m wildcards

SpaceO(N * L) for trie storage and O(L) stack space

Iterative DFS uses explicit stack instead of recursion, with similar branching complexity on wildcards.

💡 This approach avoids recursion depth limits and is useful in languages with limited stack size.

Interview Verdict: Accepted and practical alternative to recursive DFS

This approach is equally efficient but safer in environments with recursion limits.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the trie with recursive DFS (Approach 2) is the best balance of clarity and efficiency to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(N * L)	O(N * L)	No	N/A	Mention only - never code due to inefficiency
2. Trie with Recursive DFS	O(L) add, O(26^m) search worst-case	O(N * L)	Possible if deep recursion	Yes	Preferred approach to code
3. Trie with Iterative DFS	O(L) add, O(26^m) search worst-case	O(N * L)	No	Yes	Good alternative if recursion is a concern

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying requirements, then explain brute force to show understanding. Progress to trie-based solutions emphasizing wildcard handling. Practice coding and testing edge cases.

How to Present

Step 1: Clarify problem constraints and wildcard behavior.Step 2: Describe brute force approach to show baseline understanding.Step 3: Introduce trie data structure for efficient storage.Step 4: Explain DFS backtracking for wildcard '.' handling.Step 5: Code the trie with recursive or iterative search.Step 6: Test with examples and edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer checks your understanding of tries, recursion/backtracking, handling wildcards, and code correctness under edge cases.

Common Follow-ups

• How to optimize memory usage in trie? → Use arrays or compressed tries.
• Can you implement deleteWord? → Requires careful node pruning.

💡 Follow-ups test deeper trie knowledge and ability to extend the data structure.

🔍

Pattern Recognition

When to Use

1) Need to store many words efficiently, 2) Search supports wildcard '.', 3) Prefix or character-by-character matching is required, 4) Backtracking or DFS needed for wildcards.

Signature Phrases

search(word) with '.' wildcardaddWord(word) to data structure

NOT This Pattern When

Problems that only require prefix matching without wildcards or problems using hash maps for exact matches.

Similar Problems

Implement Trie (Prefix Tree) - basic trie operations without wildcardsWord Search II - DFS with backtracking on a board using trieReplace Words - prefix matching with trie

Practice

1. You are given an array of integers and a range [low, high]. You need to count the number of pairs (i, j) with i < j such that the XOR of nums[i] and nums[j] lies within the given range. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a brute force nested loop to check all pairs and count those with XOR in the range.

B. Use dynamic programming to store counts of XOR values for prefixes and combine them.

C. Sort the array and use two pointers to find pairs with XOR in the range.

D. Build a bitwise trie of the numbers and for each number, query how many previously inserted numbers produce XOR less than or equal to a limit, then combine results for the range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting pairs with XOR in a range efficiently, which brute force (nested loops) is too slow for large inputs.

2. Step 2: Identify the suitable data structure

   A bitwise trie allows efficient counting of numbers with XOR less than a limit by traversing bits from most significant to least significant.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitwise trie approach is known to solve XOR range queries optimally [OK]

Hint: Bitwise trie enables efficient XOR range counting [OK]

Common Mistakes:

• Thinking sorting + two pointers works for XOR ranges
• Assuming DP can handle XOR pairs directly
• Believing brute force is optimal

2. What is the time complexity of the optimal Trie + DFS with memoization solution for finding all concatenated words in a dictionary of n words with maximum length L?

medium

A. O(n * L^3) due to checking all substring splits recursively

B. O(n * L^2) because each word triggers DFS with memoization and Trie traversal

C. O(n^2 * L) since each word is compared against all others

D. O(n * L) as Trie insertion and lookup are linear in word length

Solution

1. Step 1: Identify outer loop over n words and inner DFS per word

   Each word triggers DFS that explores prefixes up to length L, with memoization preventing repeated work.

2. Step 2: Analyze DFS and Trie traversal costs

   DFS explores up to L positions, each prefix check is O(1) in Trie per character, total O(L^2) per word due to nested loops and memoization.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Memoization reduces exponential splits to O(L^2) per word, multiplied by n words [OK]

Hint: Memoization reduces exponential recursion to quadratic per word [OK]

Common Mistakes:

• Confusing brute force O(n*L^3) with optimized approach
• Ignoring memoization benefits

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

4. Suppose the problem is modified so that root words can be reused multiple times to replace multiple prefixes in a single word (e.g., 'catcat' could be replaced by 'catcat' if 'cat' is a root). Which modification to the trie-based approach correctly handles this variant?

hard

A. Use the existing shortest prefix search once per word; no change needed as reuse is irrelevant.

B. After finding the shortest prefix, continue searching the remaining suffix recursively for more prefixes to replace.

C. Modify search to find the longest prefix instead of shortest, then recursively replace the suffix with roots.

D. Replace the entire word only if it exactly matches a root; otherwise, leave it unchanged.

Solution

1. Step 1: Understand reuse requirement

   Words can be replaced by concatenations of multiple root prefixes, so partial replacements must continue recursively.

2. Step 2: Modify search logic

   After finding a shortest prefix, recursively apply the same prefix search on the remaining suffix to replace all possible prefixes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive prefix replacement handles multiple root reuse correctly [OK]

Hint: Recursively replace suffixes after shortest prefix [OK]

Common Mistakes:

• Stopping after first prefix
• Searching for longest prefix only

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the algorithm is necessary to correctly handle this variant?

hard

A. Modify the inner loop to continue checking all prefixes even after dp[i] is set to True

B. Change dp array to count number of ways instead of boolean flags

C. Remove the dp array and use pure recursion with memoization only

D. No change needed; the original DP with trie approach already supports reuse

Solution

1. Step 1: Understand reuse impact on DP

   When reuse is allowed, multiple segmentations can overlap. The DP must consider all possible prefixes, not stop at first True.

2. Step 2: Modify inner loop behavior

   Breaking early when dp[i] is True prevents exploring all segmentations. Removing the break allows full exploration, correctly handling reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing all prefixes ensures reuse is handled [OK]

Hint: Breaking early blocks multiple reuse paths [OK]

Common Mistakes:

• Assuming original DP supports reuse without change
• Changing dp to count ways unnecessarily
• Removing dp and relying on recursion only