Design Add and Search Words Data Structure

📋

Design Add and Search Words Data Structure

Edge cases:

</>

IDE

def addWord(self, word: str) -> None def search(self, word: str) -> boolpublic void addWord(String word) public boolean search(String word)void addWord(string word) bool search(string word)function addWord(word) function search(word)

class WordDictionary:
    def __init__(self):
        # Write your solution here
        pass

    def addWord(self, word: str) -> None:
        pass

    def search(self, word: str) -> bool:
        pass

class WordDictionary {
    public WordDictionary() {
        // Write your solution here
    }

    public void addWord(String word) {
        // Write your solution here
    }

    public boolean search(String word) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

class WordDictionary {
public:
    WordDictionary() {
        // Write your solution here
    }

    void addWord(string word) {
        // Write your solution here
    }

    bool search(string word) {
        // Write your solution here
        return false;
    }
};

class WordDictionary {
    constructor() {
        // Write your solution here
    }

    addWord(word) {
        // Write your solution here
    }

    search(word) {
        // Write your solution here
        return false;
    }
}

Common Bugs to Avoid

Wrong: true for search('') when no empty word addedNot handling empty search string explicitly, returning true or error✅ Add explicit check: if search word is empty and no empty word added, return false

Wrong: false for search with all '.' wildcards when matching words existSearch does not explore all children nodes for '.' wildcard✅ Implement DFS that explores all children nodes when '.' is encountered

Wrong: true for search of longer word than any addedSearch does not enforce exact length match, allowing prefix matches✅ Ensure search returns false if search word length exceeds any added word length

Wrong: false for search with multiple '.' wildcards when matches existGreedy search stops early, not exploring all branches for '.'✅ Use full DFS backtracking to explore all possible children for each '.'

Wrong: TLE on large inputsUsing brute force linear search over all words instead of trie✅ Implement trie with DFS wildcard search to achieve O(L) average time

✓

Test Cases

Focus on handling edge cases like empty strings and duplicates to solidify your base implementation.

Prepare to catch subtle bugs like greedy search traps and length boundary errors.

Optimize your solution to handle large inputs efficiently using trie and DFS.

t1_01basic

Input[{"method":"addWord","args":["bad"]},{"method":"addWord","args":["dad"]},{"method":"addWord","args":["mad"]},{"method":"search","args":["pad"]},{"method":"search","args":["bad"]},{"method":"search","args":[".ad"]},{"method":"search","args":["b.."]}]

Expected[null,null,null,false,true,true,true]

⏱ Performance - must finish in 2000ms

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.

💡 Think about how to store words to allow fast prefix and wildcard searches.

💡 Use a trie data structure and DFS to handle '.' wildcard characters.

💡 Implement recursive search that explores all children nodes when '.' is encountered.

Why it failed: Basic case failed - likely your search does not handle '.' wildcards correctly. Fix by adding DFS to explore all children nodes when '.' is found.

✓ Core trie insertion and wildcard search logic is correct.

t1_02basic

Input[{"method":"addWord","args":["apple"]},{"method":"addWord","args":["apply"]},{"method":"search","args":["apple"]},{"method":"search","args":["appl."]},{"method":"search","args":["a...."]},{"method":"search","args":["....."]},{"method":"search","args":["ap..e"]}]

Expected[null,null,true,true,true,true,false]

⏱ Performance - must finish in 2000ms

Added 'apple' and 'apply'. Searching 'apple' returns true. 'appl.' matches 'apple' and 'apply' so true. 'a....' matches any 5-letter word starting with 'a' so true. '.....' matches any 5-letter word so true. 'ap..e' does not match any added word so false.

💡 Check how your search handles multiple '.' wildcards in different positions.

💡 Ensure your DFS explores all possible children for each '.' in the search word.

💡 Return true if any path matches fully; do not stop at first mismatch.

Why it failed: Search failed on multiple wildcards - your DFS likely stops early or does not explore all children. Fix by fully exploring all branches for '.' characters.

✓ Wildcard search correctly handles multiple '.' characters.

t2_01edge

Input[{"method":"search","args":[""]}]

Expected[false]

⏱ Performance - must finish in 2000ms

Searching an empty string returns false because no empty words were added.

💡 Consider what happens when searching for an empty string with no words added.

💡 Check if your code handles empty search strings explicitly.

💡 Return false immediately if search word length is zero and no empty word was added.

Why it failed: Empty string search incorrectly returns true or errors. Fix by returning false if no empty word was added.

✓ Empty string search correctly returns false when no empty word exists.

t2_02edge

Input[{"method":"addWord","args":["test"]},{"method":"addWord","args":["test"]},{"method":"search","args":["test"]}]

Expected[null,null,true]

⏱ Performance - must finish in 2000ms

Adding duplicate words 'test' twice should not affect search results; searching 'test' returns true.

💡 Check if adding duplicates causes errors or changes search behavior.

💡 Ensure your data structure can handle duplicate insertions gracefully.

💡 Duplicates should not create multiple nodes or affect search correctness.

Why it failed: Duplicate addWord calls cause incorrect search results or errors. Fix by allowing duplicates without altering trie structure incorrectly.

✓ Duplicate words handled correctly without affecting search.

t2_03edge

Input[{"method":"addWord","args":["cat"]},{"method":"addWord","args":["bat"]},{"method":"addWord","args":["rat"]},{"method":"search","args":["..."]}]

Expected[null,null,null,true]

⏱ Performance - must finish in 2000ms

Searching with all '.' characters of length 3 matches any 3-letter word added, so returns true.

💡 Verify your search handles all '.' wildcards correctly.

💡 DFS should explore all children at each '.' position.

💡 Return true if any word of matching length exists.

Why it failed: Search with all '.' returns false incorrectly. Fix by exploring all children nodes for each '.' wildcard.

✓ Search with all '.' wildcards returns true correctly.

t2_04edge

Input[{"method":"addWord","args":["a"]},{"method":"search","args":["aa"]}]

Expected[null,false]

⏱ Performance - must finish in 2000ms

Searching for a word longer than any added word returns false.

💡 Check if your search enforces exact length matching.

💡 Ensure search returns false if search word length exceeds any added word length.

💡 Do not allow prefix matches to return true for longer search words.

Why it failed: Search returns true for longer words not added. Fix by enforcing exact length match in search.

✓ Search correctly returns false for longer words not added.

t3_01corner

Input[{"method":"addWord","args":["a"]},{"method":"addWord","args":["ab"]},{"method":"search","args":["a"]},{"method":"search","args":["ab"]},{"method":"search","args":["abc"]}]

Expected[null,null,true,true,false]

⏱ Performance - must finish in 2000ms

Tests exact boundary conditions: searching for words equal to added words returns true; searching longer word 'abc' returns false.

💡 Check that search returns false for words longer than any added word.

💡 Ensure your trie traversal stops correctly when search word length exceeds any path.

💡 Return false if search word length is greater than any added word length.

Why it failed: Search returns true for longer words not added. Fix by checking length boundaries during search.

✓ Search correctly returns false for longer words not added.

t3_02corner

Input[{"method":"addWord","args":["aaa"]},{"method":"addWord","args":["aab"]},{"method":"search","args":["a.a"]},{"method":"search","args":["aa."]},{"method":"search","args":["a.."]}]

Expected[null,null,true,true,true]

⏱ Performance - must finish in 2000ms

Tests wildcard search correctness with multiple '.' characters in different positions.

💡 Beware of greedy approaches that stop searching after first match.

💡 DFS must explore all possible children for each '.' to find all matches.

💡 Return true if any path matches fully; do not prune prematurely.

Why it failed: Greedy search fails to explore all branches for '.' wildcards. Fix by implementing full DFS backtracking.

✓ Wildcard search correctly explores all branches.

t3_03corner

Input[{"method":"addWord","args":["abc"]},{"method":"addWord","args":["abcd"]},{"method":"search","args":["abc"]},{"method":"search","args":["abcd"]},{"method":"search","args":["abcde"]}]

Expected[null,null,true,true,false]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded insertion: searching for longer words than added returns false.

💡 Ensure your trie does not allow partial matches beyond added word length.

💡 Check that search returns false if search word length exceeds any added word.

💡 Do not treat trie as prefix tree for search; match full length exactly.

Why it failed: Search incorrectly returns true for longer words not added. Fix by enforcing exact length match in search.

✓ Search enforces exact length match correctly.

t4_01performance

Input[{"method":"addWord","args":["aaaaaaaaaaaaaaaaaaaaaaaaa"]},{"method":"addWord","args":["bbbbbbbbbbbbbbbbbbbbbbbbb"]},{"method":"addWord","args":["ccccccccccccccccccccccccc"]},{"method":"addWord","args":["ddddddddddddddddddddddddd"]},{"method":"addWord","args":["eeeeeeeeeeeeeeeeeeeeeeeee"]},{"method":"addWord","args":["ffffffffffffffffffffffffff"]},{"method":"addWord","args":["ggggggggggggggggggggggggg"]},{"method":"addWord","args":["hhhhhhhhhhhhhhhhhhhhhhhhh"]},{"method":"addWord","args":["iiiiiiiiiiiiiiiiiiiiiiiii"]},{"method":"addWord","args":["jjjjjjjjjjjjjjjjjjjjjjjjj"]},{"method":"search","args":["aaaaaaaaaaaaaaaaaaaaaaaaa"]},{"method":"search","args":[".........................."]},{"method":"search","args":["zzzzzzzzzzzzzzzzzzzzzzzzz"]}]

Expectednull

⏱ Performance - must finish in 2000ms

Performance test with 10 words of max length 25 and searches including all '.' wildcards. n=10, L=25, must complete in 2s.

💡 Trie insertion and search should be O(L) on average.

💡 DFS search with wildcards can be expensive; optimize pruning.

💡 Avoid brute force linear search over all words for performance.

Why it failed: TLE due to brute force linear search over all words. Fix by implementing trie with DFS wildcard search.

✓ Trie-based solution passes performance constraints.

Practice

1. Given the following Trie implementation, after inserting the words ['cat', 'car', 'dog'], what is the value of node.isEnd after processing the last character of 'car' in the insert method?

easy

A. false, because 'car' shares prefix with 'cat' and 'dog'

B. true, but only if 'car' was inserted before 'cat'

C. false, because isEnd is only set after inserting all words

D. true, because 'car' is a complete inserted word

Solution

1. Step 1: Trace insertion of 'car'

   For each character 'c', 'a', 'r', nodes are created or reused. After last character 'r', node.isEnd is set to true.

2. Step 2: Confirm isEnd flag meaning

   isEnd marks the end of a complete word. Since 'car' was inserted, node.isEnd after 'r' is true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   isEnd is true after inserting 'car' [OK]

Hint: isEnd is set true after inserting each complete word [OK]

Common Mistakes:

• Assuming isEnd is false if prefix overlaps with other words

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

3. What is the time complexity of the optimal trie-based solution for finding shortest unique prefixes for n words each of maximum length m?

medium

A. O(n^2 * m) because each prefix is compared with all other words

B. O(n * m) because each word is inserted and traversed once in the trie

C. O(n * m^2) due to nested prefix checks during insertion

D. O(n * log n * m) because sorting is involved before trie insertion

Solution

1. Step 1: Identify operations per word

   Each word of length m is inserted into the trie once, updating frequency counts along the path.

2. Step 2: Analyze total complexity

   Insertion and prefix search both take O(m) per word, so total is O(n * m). No sorting or nested loops over words occur.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie insertion and search scale linearly with total characters [OK]

Hint: Trie operations scale with total characters, not pairwise comparisons [OK]

Common Mistakes:

• Confusing trie insertion with pairwise prefix checks
• Assuming sorting is required

4. What is the time complexity of the optimal Word Break solution that uses iterative DP combined with a reversed trie for prefix checks, where n is the length of the string and m is the maximum length of words in the dictionary?

medium

A. O(n * log m) due to binary search in trie children

B. O(n^2) because of nested loops over the string

C. O(n * m) because for each position, trie traversal is bounded by max word length

D. O(n * m^2) because each trie traversal can take up to m steps and each step checks children

Solution

1. Step 1: Identify loops and trie traversal cost

   Outer loop runs n times. Inner loop traverses backwards up to m characters (max word length). Trie traversal per character is O(1) on average due to hashmap children.

2. Step 2: Combine to get total complexity

   Total time is O(n * m). Nested loops do not run n^2 because inner loop breaks early when no trie child exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie traversal bounded by max word length m [OK]

Hint: Trie traversal limits inner loop to max word length [OK]

Common Mistakes:

• Assuming inner loop always runs n times
• Confusing trie traversal cost with binary search
• Ignoring early breaks in inner loop

5. If the problem is modified so that words can be concatenated using the same shorter word multiple times (reuse allowed), which change to the Trie + DFS + memoization approach is necessary to correctly find all concatenated words?

hard

A. Keep memoization but ensure that the base case allows concatenations with repeated words

B. Remove memoization to allow repeated exploration of the same indices

C. No change needed; current memoization handles reuse correctly

D. Modify DFS to allow revisiting the same start index multiple times without memoization

Solution

1. Step 1: Understand reuse means words can be concatenated multiple times

   Memoization caches results per start index; reuse is allowed if base case and DFS logic permit repeated words.

2. Step 2: Adjust base case and DFS to allow repeated words but keep memoization for efficiency

   Memoization should remain to avoid exponential calls; base case must allow concatenations with repeated words.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization remains; base case and DFS logic adapt to reuse [OK]

Hint: Memoization is key; only base case and DFS logic need adjustment for reuse [OK]

Common Mistakes:

• Removing memoization causes TLE
• Ignoring base case changes for reuse