Word Search II

📋

Problem

Imagine you have a large grid of letters and a dictionary of words. Your task is to find all words from the dictionary that can be formed by tracing adjacent letters in the grid, like a word puzzle challenge.

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. Return all words found in the board.

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

Edge cases: Empty board → returns empty listEmpty words list → returns empty listWords with repeated letters that require revisiting cells → should not be found

</>

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: Includes words that require revisiting the same cell multiple timesNot tracking visited cells properly during backtracking✅ Add a visited set per word search and skip cells already visited in current path

Wrong: Includes words formed by diagonal adjacencyNeighbor exploration includes diagonal cells incorrectly✅ Restrict neighbor moves to only up, down, left, and right directions

Wrong: Misses valid words due to greedy early stopping after first found pathStopping search prematurely without exploring all paths✅ Continue backtracking to explore all possible paths for each word

Wrong: Fails or returns non-empty on empty board or empty words inputNo guard clauses for empty inputs✅ Add early return for empty board or empty words list

Wrong: TLE on large inputs due to brute force per wordNot using trie prefix pruning, searching each word independently✅ Build a trie of words and prune backtracking paths early

✓

Test Cases

Handle empty inputs and small boards carefully to avoid crashes.

Check adjacency rules and avoid greedy pruning traps.

Implement trie-based prefix pruning to handle large inputs efficiently.

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.

💡 Try searching each word by backtracking from each cell.

💡 Use a trie to prune searches early when no prefix matches.

💡 Mark visited cells to avoid revisiting in the same word path.

Why it failed: Failed to find correct words or included invalid words. Possibly missing visited cell checks or prefix pruning. Fix by implementing backtracking with visited set and trie prefix checks.

✓ Correctly found all valid words from the board.

t1_02basic

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

Expected["ab","ad"]

⏱ Performance - must finish in 2000ms

Only 'ab' and 'ad' can be formed by adjacent letters; 'abc', 'abd', 'abcd' require revisiting cells or invalid paths.

💡 Check adjacency and ensure no cell is reused in the same word.

💡 Use backtracking with pruning to avoid invalid paths early.

💡 Verify that word paths do not revisit cells and match board letters.

Why it failed: Incorrectly included words requiring revisiting cells or invalid adjacency. Fix by enforcing visited cell tracking and adjacency rules strictly.

✓ Correctly filtered out invalid words and found only valid ones.

t2_01edge

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

Expected[]

⏱ Performance - must finish in 2000ms

Empty board means no words can be found.

💡 Check if the board is empty before searching.

💡 Return empty list immediately if board has no rows.

💡 Add a guard clause to handle empty board input.

Why it failed: Code crashes or returns non-empty result on empty board. Fix by adding a check for empty board and returning empty list early.

✓ Handles empty board input gracefully by returning empty list.

t2_02edge

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

Expected[]

⏱ Performance - must finish in 2000ms

Empty words list means no words to find, so return empty list.

💡 Check if words list is empty before searching.

💡 Return empty list immediately if no words given.

💡 Add a guard clause to handle empty words input.

Why it failed: Code returns non-empty result or crashes on empty words list. Fix by adding a check for empty words and returning empty list early.

✓ Handles empty words input gracefully by returning empty list.

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 that are substrings of repeated 'a's without revisiting cells.

💡 Consider multiple paths for repeated letters without revisiting cells.

💡 Use backtracking with visited set to avoid cell reuse but allow different paths.

💡 Ensure your algorithm explores all valid paths for repeated letters.

Why it failed: Fails to find longer repeated-letter words due to incorrect visited logic or pruning. Fix by correctly tracking visited cells per path and exploring all neighbors.

✓ Correctly finds all repeated-letter words without revisiting cells.

t3_01corner

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

Expected[]

⏱ Performance - must finish in 2000ms

Word requires diagonal moves which are invalid; only horizontal and vertical adjacency allowed.

💡 Remember adjacency is only horizontal and vertical, not diagonal.

💡 Check your neighbor exploration directions carefully.

💡 Fix neighbor checks to exclude diagonal cells.

Why it failed: Incorrectly finds words using diagonal adjacency. Fix by restricting neighbor moves to only up/down/left/right only.

✓ Correctly excludes words requiring diagonal adjacency.

t3_02corner

Input{"board":[["a","b","c"],["a","e","f"],["a","h","i"]],"words":["aaa","aa"]}

Expected["aa","aaa"]

⏱ Performance - must finish in 2000ms

Tests correct handling of multiple identical letters and no revisiting cells; ensures 0/1 usage per cell.

💡 Ensure each cell is used at most once per word path.

💡 Avoid counting the same cell multiple times for repeated letters.

💡 Use a visited set cleared per word search to enforce 0/1 usage.

Why it failed: Incorrectly allows reusing the same cell multiple times in a word. Fix by tracking visited cells per path and disallow revisits.

✓ Correctly enforces 0/1 usage of each cell per word.

t3_03corner

Input{"board":[["c","a","t"],["r","r","e"],["t","o","n"]],"words":["cat","car","cart","tone","toe"]}

Expected["cat","car","tone","toe"]

⏱ Performance - must finish in 2000ms

Tests greedy trap: picking first matching letter path may miss valid words; requires full backtracking.

💡 Avoid greedy early pruning that stops after first found path.

💡 Explore all possible paths for each word to find all matches.

💡 Implement full backtracking with trie prefix pruning.

Why it failed: Misses valid words due to greedy early stopping. Fix by exploring all paths and using trie to prune invalid prefixes.

✓ Finds all valid words by exhaustive backtracking with pruning.

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":["abc","mnop","qrst","uvwx","yzab","cdefg","hijkl","mnopq","rstuv","wxyz","abcdefghij","klmnopqrst","uvwxyzabcd","efghijklmn","opqrstuvwx","yzabcdefg","hijklmnopq","rstuvwxyz","abcdefgh","ijklmnop","qrstuvwx","yzabcdef","ghijklmn","opqrstuv","wxyzabcd","efghijkl","mnopqrst","uvwxyzab","cdefghij","klmnopqr","stuvwxyz","abcdefghij","klmnopqrst","uvwxyzabcd","efghijklmn","opqrstuvwx","yzabcdefg","hijklmnopq","rstuvwxyz","abcdefgh","ijklmnop","qrstuvwx","yzabcdef","ghijklmn","opqrstuv","wxyzabcd","efghijkl","mnopqrst","uvwxyzab","cdefghij","klmnopqr","stuvwxyz","abcdefghij","klmnopqrst","uvwxyzabcd","efghijklmn","opqrstuvwx","yzabcdefg","hijklmnopq","rstuvwxyz","abcdefgh","ijklmnop","qrstuvwx","yzabcdef","ghijklmn","opqrstuv","wxyzabcd","efghijkl","mnopqrst","uvwxyzab","cdefghij","klmnopqr","stuvwxyz","abcdefghij","klmnopqrst","uvwxyzabcd","efghijklmn","opqrstuvwx","yzabcdefg","hijklmnopq","rstuvwxyz","abcdefgh","ijklmnop","qrstuvwx","yzabcdef","ghijklmn","opqrstuv","wxyzabcd","efghijkl","mnopqrst","uvwxyzab","cdefghij","klmnopqr","stuvwxyz","abcdefghij","klmnopqrst"]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 12x12 board with 100 words tests O(N*M*4^L) complexity; must complete within 2 seconds.

💡 Brute force per word is too slow; use trie to prune searches.

💡 Backtracking with prefix pruning reduces search space drastically.

💡 In-place board marking and early pruning optimize performance.

Why it failed: TLE due to brute force backtracking for each word. Fix by implementing trie-based prefix pruning and efficient backtracking.

✓ Efficient trie-based backtracking passes within time limit.

Practice

1. You need to transform one string into another using the minimum number of insertions, deletions, and substitutions. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Greedy algorithm that replaces characters whenever they differ

B. Pure brute force recursion without memoization

C. Dynamic Programming that builds a table of subproblem solutions based on prefixes

D. Divide and conquer by splitting strings into halves and solving independently

Solution

1. Step 1: Understand problem requires minimum edits

   The problem asks for minimum insertions, deletions, and substitutions to convert one string to another, which is a classic DP problem.

2. Step 2: Identify approach guaranteeing optimal substructure

   Dynamic Programming builds solutions for prefixes and combines them, ensuring optimality and polynomial time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP table approach is standard for edit distance [OK]

Hint: Edit distance requires DP over prefixes [OK]

Common Mistakes:

• Thinking greedy or divide-and-conquer works optimally

2. You are given an array representing the heights of adjacent bars in a histogram. The task is to find the largest rectangular area that can be formed within the bounds of the histogram bars. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Greedy approach selecting the tallest bar and expanding outwards

B. Brute force nested loops checking all possible rectangles

C. Dynamic programming with memoization of subproblems

D. Single pass stack-based approach that tracks indices of bars

Solution

1. Step 1: Understand problem constraints and requirements

   The problem requires finding the largest rectangle in a histogram efficiently, which involves checking contiguous bars and their heights.

2. Step 2: Identify optimal approach using stack

   The single pass stack-based approach uses a stack to keep track of indices of bars in ascending order, allowing calculation of maximal rectangle areas in O(n) time by popping bars when a smaller height is encountered.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach is known optimal for largest rectangle in histogram [OK]

Hint: Stack-based approach achieves O(n) time [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing this with a DP problem
• Thinking greedy expansion from tallest bar suffices

3. Given the following Python code snippet implementing the merge step of the skyline problem, and the input skylines left = [[1, 3], [5, 0]] and right = [[2, 4], [6, 0]], what is the value of the variable merged after the while loop completes (before extending remaining points)?

easy

A. [[1, 3], [2, 4], [5, 0], [6, 0]]

B. [[1, 3], [2, 4]]

C. [[1, 3], [2, 4], [5, 0]]

D. [[1, 3], [2, 4], [5, 0], [6, 0], [7, 0]]

Solution

1. Step 1: Trace first iteration

   left[0] = [1,3], right[0] = [2,4]. Since 1 < 2, x=1, h1=3, h2=0, maxH=3 -> merged = [[1,3]]

2. Step 2: Trace second iteration

   left[1] = [5,0], right[0] = [2,4]. Since 2 < 5, x=2, h2=4, h1=3 (from previous), maxH=4 -> merged = [[1,3],[2,4]]

3. Step 3: Trace third iteration

   left[1] = [5,0], right[1] = [6,0]. Since 5 < 6, x=5, h1=0, h2=4 (previous), maxH=4 -> merged = [[1,3],[2,4],[5,0]]

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Correctly merged points before extending remaining [OK]

Hint: Trace pointer increments carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Forgetting to update h1 or h2 correctly
• Appending points with same height consecutively
• Misaligning indices causing skipped points

4. Examine the following modified code snippet for the Alien Dictionary problem. Which line contains a subtle bug that can cause incorrect results on certain inputs?

medium

A. Line incrementing in_degree[w2[j]] after adding edge

B. Missing prefix invalid case check after min_len calculation

C. Line checking if w2[j] not in graph[w1[j]] before adding edge

D. Line initializing queue with characters having zero in-degree

Solution

1. Step 1: Identify missing prefix invalid case check

   Code lacks check for case where longer word precedes its prefix (e.g., "abc" before "ab"), which is invalid.

2. Step 2: Understand consequences of missing this check

   Without this, function may return incorrect order or fail to detect invalid input.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Prefix invalid case is critical for correctness [OK]

Hint: Look for missing validation of prefix ordering [OK]

Common Mistakes:

• Ignoring prefix invalid case
• Adding duplicate edges
• Incorrect in-degree updates

5. Suppose the problem is modified so that nodes can be revisited multiple times without penalty, but the goal remains to visit all nodes at least once with the shortest path length. Which modification to the bidirectional BFS with state compression algorithm is necessary to handle this variant correctly?

hard

A. Remove the visited bitmask and track only the current node in BFS states

B. Modify the bitmask to track the count of visits per node instead of a binary visited flag

C. Use a simple BFS without bitmask since revisits are allowed and shortest path is trivial

D. Keep the visited bitmask but allow revisiting states with the same mask and node multiple times

Solution

1. Step 1: Understand problem change

   Allowing multiple revisits without penalty means the visited state must track how many times each node is visited if that affects path validity.

2. Step 2: Modify state representation

   Binary bitmask is insufficient; need to track counts per node, e.g., using a vector or multi-bit encoding per node, to correctly represent states and avoid incorrect pruning.

3. Step 3: Implication on BFS

   State space grows, but correctness requires this richer state representation to find shortest path under new rules.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting visits per node is necessary when revisits are allowed without penalty [OK]

Hint: Bitmask alone can't track multiple visits; need counts per node [OK]

Common Mistakes:

• Removing bitmask entirely loses track of visited nodes
• Allowing revisits without state changes causes incorrect pruning
• Assuming simple BFS suffices without state tracking