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 finding the longest word in a dictionary, what is the value of the variable longest after processing the input ["a", "app", "ap", "apply"]?

easy

A. "apply"

B. "app"

C. "ap"

D. "a"

Solution

1. Step 1: Insert words into trie

   Words "a", "app", "ap", "apply" are inserted. Only nodes with complete words have word attribute set.

2. Step 2: BFS traversal and update longest

   Traversal visits "a" first, then "ap", then "app". "apply" is not valid because "appl" prefix is missing. The longest valid word found is "app".

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   "app" is longest word with all prefixes present [OK]

Hint: Check prefix presence during BFS to update longest [OK]

Common Mistakes:

• Assuming "apply" is valid without all prefixes
• Not updating longest correctly on equal length
• Skipping lex order in BFS children iteration

2. You need to design a system that receives a continuous stream of characters and must efficiently determine if any suffix of the stream matches a word from a given dictionary. Which algorithmic approach best guarantees optimal query time and memory usage?

easy

A. Build a trie of the reversed dictionary words and maintain a limited-length stream buffer to traverse the trie backwards on each query.

B. Use a brute force approach that checks all suffixes of the stream against the dictionary on every query.

C. Use a prefix trie of the dictionary words and scan the stream from the start to check for matches.

D. Apply dynamic programming to store all possible substrings of the stream and check membership in the dictionary.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if any suffix of the stream matches a dictionary word efficiently, which suggests suffix-based matching.

2. Step 2: Evaluate approaches

   Brute force checking all suffixes is too slow. Prefix tries do not help with suffix matching. Dynamic programming for all substrings is inefficient. Building a trie of reversed words and traversing it backwards with a limited buffer optimizes both time and space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversed trie + limited buffer matches suffixes efficiently [OK]

Hint: Suffix matching needs reversed trie traversal [OK]

Common Mistakes:

• Using prefix trie for suffix matching
• Checking all suffixes brute force
• Using DP on all substrings

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

4. The following code attempts to build a trie to find shortest unique prefixes. Which line contains a subtle bug that causes incorrect prefix results?

medium

A. Line where node.freq is checked in unique_prefix method

B. Line where node.children[ch] is created if missing

C. Line where node.freq is incremented during insertion (missing here)

D. Line where prefix is concatenated with ch in unique_prefix

Solution

1. Step 1: Identify frequency update location

   Frequency must be incremented at each node during insertion to track how many words pass through.

2. Step 2: Locate missing increment

   The code does not increment node.freq inside the insertion loop, so frequencies remain zero, causing unique_prefix to fail.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Without freq increments, unique prefix detection breaks [OK]

Hint: Frequency increment must be inside insertion loop [OK]

Common Mistakes:

• Forgetting to increment frequency at each node
• Checking freq before incrementing

5. Suppose the WordDictionary is extended to support searching for words with the wildcard '*' that matches zero or more characters (instead of '.' matching exactly one). Which of the following modifications to the trie search algorithm correctly handles '*' wildcard searches?

hard

A. Use recursion or stack to explore zero or more characters by branching at current node and advancing index accordingly.

B. Treat '*' as '.' and continue with single character branching only.

C. Precompute all possible expansions of '*' and store them in the trie during addWord.

D. Ignore '*' and treat it as a literal character during search.

Solution

1. Step 1: Understand '*' wildcard semantics

   '*' matches zero or more characters, so search must explore skipping '*' or consuming characters.

2. Step 2: Identify correct search strategy

   Using recursion or stack to explore both skipping '*' (index+1) and consuming children (index unchanged) correctly handles zero or more matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Branching on both skipping and consuming characters handles '*' wildcard [OK]

Hint: '*' requires branching on skip or consume [OK]

Common Mistakes:

• Treating '*' like '.'
• Precomputing expansions is infeasible
• Ignoring '*' wildcard semantics