Word Search II (Multiple Words in Grid)

📋

Problem

Imagine you have a giant crossword puzzle and a huge dictionary of words. You want to find all the words from the dictionary that appear in the puzzle by connecting adjacent letters.

Given a 2D board of characters and a list of words, find all words in the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

1 <= board.length, board[i].length <= 121 <= words.length <= 3 * 10^41 <= words[i].length <= 10board and words consist of lowercase English letters

Edge cases: Empty board → returns empty listEmpty words list → returns empty listWords with repeated letters requiring careful backtracking → correct detection

</>

IDE

def findWords(board: List[List[str]], words: List[str]) -> List[str]:public List<String> findWords(char[][] board, String[] words)vector<string> findWords(vector<vector<char>>& board, vector<string>& words)function findWords(board, words)

def findWords(board, words):
    # Write your solution here
    pass

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        // Write your solution here
        return new ArrayList<>();
    }
}

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

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    // Write your solution here
    return {};
}

function findWords(board, words) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Missing some valid wordsDFS does not explore all paths or trie pruning is incorrect.✅ Implement full DFS with backtracking and prune using trie prefixes.

Wrong: Includes invalid words not present in boardNo prefix pruning or incorrect visited cell tracking.✅ Use trie to prune invalid prefixes and mark visited cells properly.

Wrong: Crashes or errors on empty board or wordsNo guard clauses for empty inputs.✅ Add checks for empty board or empty words before processing.

Wrong: Reuses cells multiple times in same wordVisited cells not tracked or unmarked correctly.✅ Track visited cells per DFS path and unmark after recursion.

Wrong: Solution times out on large inputsBrute force DFS per word without trie pruning.✅ Build trie for all words and prune DFS paths early.

✓

Test Cases

Focus on handling empty inputs and repeated letters carefully.

Watch out for greedy traps and cell reuse mistakes.

Optimize your solution with trie pruning to pass performance tests.

t1_01basic

Input{"board":[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],"words":["oath","pea","eat","rain"]}

Expected["eat","oath"]

⏱ Performance - must finish in 2000ms

The words 'eat' and 'oath' can be formed by adjacent letters in the board, while 'pea' and 'rain' cannot.

💡 Use a trie to store all words for efficient prefix checking.

💡 Perform DFS on the board, pruning paths not in the trie.

💡 Remove found words from trie nodes to avoid duplicates and speed up.

Why it failed: Failed to find correct words or included invalid words. Likely missing trie pruning or incorrect DFS backtracking. Fix by implementing trie prefix checks and marking visited cells properly.

✓ Correctly found all valid words using trie and DFS with pruning.

t1_02basic

Input{"board":[["a","b"],["c","d"]],"words":["ab","abc","abd","abcd","acdb"]}

Expected["ab","acdb"]

⏱ Performance - must finish in 2000ms

Only 'ab' and 'acdb' can be formed by adjacent letters in the small 2x2 board; 'abc', 'abd', and 'abcd' cannot be formed due to adjacency constraints.

💡 Check all possible paths starting from each cell.

💡 Use trie to prune invalid prefixes early.

💡 Ensure backtracking correctly unmarks visited cells to explore all paths.

Why it failed: Missing some valid words due to incorrect backtracking or incomplete trie traversal. Fix by ensuring visited cells are unmarked after DFS calls and trie nodes are correctly traversed.

✓ All valid words found with correct backtracking and trie usage.

t2_01edge

Input{"board":[],"words":["a","b"]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty board cannot form any words.

💡 Check for empty board input before processing.

💡 Return empty list immediately if board is empty.

💡 Avoid running DFS if board or board[0] is empty.

Why it failed: Code crashes or returns non-empty result on empty board. Fix by adding guard clauses for empty board input.

✓ Correctly returns empty list for empty board.

t2_02edge

Input{"board":[["a"]],"words":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty words list means no words to find.

💡 Check for empty words list before processing.

💡 Return empty list immediately if words list is empty.

💡 Avoid building trie or DFS if no words given.

Why it failed: Code returns non-empty result or crashes on empty words list. Fix by adding guard clause for empty words input.

✓ Correctly returns empty list for empty words input.

t2_03edge

Input{"board":[["a","a","a"],["a","a","a"],["a","a","a"]],"words":["aaa","aaaa","aaaaa"]}

Expected["aaa","aaaa","aaaaa"]

⏱ Performance - must finish in 2000ms

Board with all identical letters can form words with repeated letters requiring careful backtracking.

💡 Ensure visited cells are tracked to avoid reusing same cell in a word.

💡 Backtracking must unmark visited cells after recursion.

💡 Trie pruning helps avoid redundant searches for prefixes.

Why it failed: Fails to find longer words due to reusing cells or incorrect visited tracking. Fix by properly marking/unmarking visited cells during DFS.

✓ Correctly finds all repeated-letter words with proper backtracking.

t3_01corner

Input{"board":[["a","b","c"],["a","e","d"],["a","f","g"]],"words":["abcdefg","gfedcba"]}

Expected["abcdefg"]

⏱ Performance - must finish in 2000ms

Greedy approach fails here: only 'abcdefg' can be formed by adjacent letters, 'gfedcba' cannot.

💡 Do not greedily pick letters; explore all paths with backtracking.

💡 Use trie to prune invalid prefixes early.

💡 Check all neighbors recursively, not just first matching letter.

Why it failed: Greedy approach returns both words or misses 'abcdefg'. Fix by implementing full DFS with trie pruning instead of greedy search.

✓ Correctly finds only 'abcdefg' using full DFS and trie pruning.

t3_02corner

Input{"board":[["a","b","c"],["d","e","f"],["g","h","i"]],"words":["abc","abcdef","abcdefghi"]}

Expected["abc","abcdef","abcdefghi"]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 usage of cells: each cell can be used once per word, not unlimited times.

💡 Ensure visited cells are tracked per word search.

💡 Do not reuse cells multiple times in the same word.

💡 Backtracking must unmark visited cells after recursion.

Why it failed: Incorrectly finds longer words by reusing cells multiple times. Fix by tracking visited cells and forbidding reuse in same word.

✓ Correctly finds all words respecting 0/1 usage of cells.

t3_03corner

Input{"board":[["a","b","c","d"],["e","f","g","h"],["i","j","k","l"]],"words":["afk","bfj","cgl","dhl"]}

Expected["afk","bfj","cgl","dhl"]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in indexing neighbors and DFS boundaries.

💡 Check boundary conditions when exploring neighbors.

💡 Ensure indices do not go out of board bounds.

💡 Verify visited marking/unmarking is consistent.

Why it failed: Misses words due to off-by-one errors or invalid neighbor checks. Fix by carefully checking indices and visited logic.

✓ Correctly finds all words with proper boundary checks.

t4_01performance

Input{"board":[["a","b","c","d","e","f","g","h","i","j","k","l"],["m","n","o","p","q","r","s","t","u","v","w","x"],["y","z","a","b","c","d","e","f","g","h","i","j"],["k","l","m","n","o","p","q","r","s","t","u","v"],["w","x","y","z","a","b","c","d","e","f","g","h"],["i","j","k","l","m","n","o","p","q","r","s","t"],["u","v","w","x","y","z","a","b","c","d","e","f"],["g","h","i","j","k","l","m","n","o","p","q","r"],["s","t","u","v","w","x","y","z","a","b","c","d"],["e","f","g","h","i","j","k","l","m","n","o","p"],["q","r","s","t","u","v","w","x","y","z","a","b"],["c","d","e","f","g","h","i","j","k","l","m","n"]],"words":["abcdefghij","klmnopqrst","uvwxyzabcd","efghijklmn","opqrstuvwx","yzabcdefgh","ijklmnopqr","stuvwxyzab","cdefghijkl","mnopqrstuv","wxyzabcdef","ghijklmnop","rstuvwxyz","defghijklm","nopqrstuvw","xyzabcdefg","hijklmnopq","tuvwxyzabc","efghijklmn","pqrstuvwxy","zabcdefgh","jklmnopqrs","uvwxyzabc","fghijklmn","rstuvwxyza","bcdefghijk","lmnopqrst","vwxyzabcd","ghijklmnop","stuvwxyzab"]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 12x12 board with 30 words of length up to 10 to test performance of trie + DFS pruning approach within 2 seconds.

💡 Use trie to prune invalid prefixes early to reduce search space.

💡 Avoid redundant DFS by removing found words from trie nodes.

💡 Implement efficient visited marking and backtracking.

Why it failed: TLE occurs due to brute force or missing trie pruning. Fix by implementing trie-based prefix pruning and efficient backtracking.

✓ Solution runs within time limit using trie + DFS pruning.

Practice

1. Given the following code snippet for MapSum, after inserting keys "apple" with value 3 and "app" with value 2, what is the value of node.sum at the trie node corresponding to 'p' (the second character) after the second insert?

easy

A. 3

B. 5

C. 2

D. 0

Solution

1. Step 1: Trace insert of "apple" with value 3

   Delta = 3 - 0 = 3. Root.sum += 3 -> 3. For each character 'a','p','p','l','e', node.sum += 3. After first insert, node at second 'p' has sum 3.

2. Step 2: Trace insert of "app" with value 2

   Delta = 2 - 0 = 2. Root.sum += 2 -> 5. For 'a','p','p', node.sum += 2. Node at second 'p' sum was 3, now 3 + 2 = 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum at second 'p' after both inserts is 5 [OK]

Hint: Sum accumulates delta on each insert per prefix node [OK]

Common Mistakes:

• Forgetting to add delta on second insert
• Confusing first and second 'p' nodes
• Using old value instead of delta

2. You are given an array of integers and multiple queries. Each query provides a number x and a limit m. For each query, you must find the maximum XOR of x with any array element less than or equal to m. Which approach guarantees an optimal solution for large inputs?

easy

A. Sort the array and queries, then use a bitwise trie to insert elements up to the query limit and find max XOR.

B. Use dynamic programming to store XOR results for all subarrays and answer queries in O(1).

C. Use a brute force nested loop checking all elements for each query.

D. Apply a greedy approach by always choosing the element with the highest value less than or equal to m.

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; DP for subarrays doesn't apply since queries are arbitrary.

2. Step 2: Recognize the pattern

   Sorting nums and queries allows incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + trie insertion matches known optimal approach [OK]

Hint: Sort queries and nums, then use bit trie [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Using DP for unrelated subproblems
• Greedy max element doesn't guarantee max XOR

3. The following code attempts to answer maximum XOR queries with constraints using a bit trie. Which line contains a subtle bug that can cause incorrect results or runtime errors when no nums ≤ m are available?

medium

A. Line: node = node.children[bit]

B. Line: if not node.children[bit]: node.children[bit] = TrieNode()

C. Line: node = self.root

D. Line: if node.children[toggled_bit]:

Solution

1. Step 1: Identify empty trie scenario

   If no nums ≤ m, trie is empty; node.children[bit] can be None.

2. Step 2: Check max_xor traversal

   Line assigning node = node.children[bit] assumes child exists, causing runtime error or wrong result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Must handle empty child case to avoid errors [OK]

Hint: Check for None before descending trie [OK]

Common Mistakes:

• Ignoring empty trie case
• Assuming children always exist
• Not returning -1 when no valid nums

4. Examine the following buggy code snippet for palindrome pairs using Trie + DFS. Which line contains the subtle bug that causes missing pairs involving empty strings?

medium

A. No special handling for empty string in add_word or search

B. Line checking is_palindrome(word[:len(word)-i]) in add_word

C. Line checking if node.index >= 0 and node.index != index in search

D. Line setting node.index = index after insertion

Solution

1. Step 1: Identify empty string edge case

   Empty string pairs with palindromes require special handling to add pairs involving empty string indices.

2. Step 2: Check code for empty string handling

   Neither add_word nor search explicitly handle empty string cases, causing missing pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Empty string handling is a known subtle bug [OK]

Hint: Empty string pairs require explicit checks [OK]

Common Mistakes:

• Assuming palindrome checks cover empty strings
• Missing empty string special case
• Confusing index assignments

5. Examine the following buggy code snippet for building the trie and collecting suggestions. Which line contains the subtle bug that can cause incorrect suggestion ordering or runtime errors?

medium

A. Line with 'products.sort()' missing before building trie

B. Line with 'for product in products:' loop

C. Line with 'if len(node.suggestions) < 3:' condition

D. Line with 'if node and ch in node.children:' during search

Solution

1. Step 1: Identify missing sorting

   The code does not sort products before building the trie, so suggestions are appended in input order, not lex order.

2. Step 2: Consequences of missing sort

   Without sorting, the suggestions list at each node is not guaranteed to be lexicographically smallest three, violating problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting before trie build is essential for correct lex order [OK]

Hint: Always sort products before building trie for lex order [OK]

Common Mistakes:

• Forgetting to sort products
• Appending suggestions without limit
• Not handling missing prefix nodes