Word Search II (Trie + Backtrack)

📋

Problem

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

Given a 2D board of characters and a list of words, find all words on 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 listWords list empty → 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: List[List[str]], words: List[str]) -> List[str]:
    # 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 diagonal adjacencyDFS explores diagonal neighbors incorrectly✅ Restrict DFS moves to only up/down/left/right directions

Wrong: Includes words that reuse the same cell multiple timesVisited cells not marked or unmarked properly during backtracking✅ Mark cell as visited before recursion and unmark after recursion returns

Wrong: Returns non-empty result on empty board or empty words listNo guard clauses for empty inputs✅ Add checks to return empty list if board or words list is empty

Wrong: Times out on large inputsBrute force search for each word without Trie pruning✅ Implement Trie to prune DFS paths and avoid redundant searches

Wrong: Includes words that skip letters or jump cellsBacktracking allows non-adjacent moves or skips visited marking✅ Ensure DFS only moves to adjacent cells and respects visited marking

✓

Test Cases

Focus on handling empty inputs and minimal boards to avoid crashes.

Check adjacency rules and visited cell marking to avoid invalid words.

Optimize your solution with Trie pruning and in-place board marking to handle large inputs.

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 on the board, 'pea' and 'rain' cannot.

💡 Try building a prefix tree (Trie) for all words to prune searches early.

💡 Use backtracking with DFS on the board, pruning paths not matching any prefix in the Trie.

💡 Mark visited cells in-place or with a visited array and remove words from Trie once found to avoid duplicates.

Why it failed: Failed to find correct words or included invalid words. Likely missing prefix pruning or incorrect backtracking. Fix by implementing Trie-based pruning and careful visited marking.

✓ Correctly found all valid words using Trie and backtracking.

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 non-adjacent or repeated cells.

💡 Check adjacency constraints carefully; letters must be horizontally or vertically adjacent.

💡 Ensure you do not reuse the same cell multiple times in a single word.

💡 Use Trie to prune searches early when no prefix matches.

Why it failed: Incorrectly included words requiring diagonal or repeated cells. Fix by enforcing adjacency and visited cell constraints strictly.

✓ Correctly enforced adjacency and no reuse of cells.

t2_01edge

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

Expected[]

⏱ Performance - must finish in 2000ms

Empty board means no words can be formed.

💡 Check for empty board input before processing.

💡 Return empty list immediately if board is empty or has zero rows.

💡 Avoid index errors by validating board dimensions.

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

✓ Correctly handles empty board 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.

💡 Avoid unnecessary processing when words list is empty.

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

✓ Correctly returns empty list when no words to search.

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 all words of repeated 'a's up to length 5.

💡 Ensure backtracking correctly handles repeated letters and does not reuse cells.

💡 Use visited marking to avoid revisiting same cell in one word path.

💡 Trie pruning helps avoid redundant searches for prefixes not in words.

Why it failed: Fails to find longer repeated-letter words or revisits cells incorrectly. Fix by proper visited marking and backtracking.

✓ Correctly finds all repeated-letter words without cell reuse.

t3_01corner

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

Expected["abc","cfi"]

⏱ Performance - must finish in 2000ms

'abc' and 'cfi' can be formed by adjacent horizontal/vertical moves; 'aei' and 'beh' require diagonal moves which are invalid.

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

💡 Check your DFS directions carefully to exclude diagonals.

💡 Fix by limiting DFS moves to up/down/left/right only.

Why it failed: Incorrectly includes words requiring diagonal adjacency. Fix by restricting DFS to four directions only.

✓ Correctly excludes diagonal adjacency words.

t3_02corner

Input{"board":[["a","b","c","d"],["e","f","g","h"],["i","j","k","l"],["m","n","o","p"]],"words":["abcd","abcf","mnop","mnopq"]}

Expected["abcd","mnop"]

⏱ Performance - must finish in 2000ms

'abcd' and 'mnop' can be formed by adjacent letters; 'abcf' requires skipping letters and 'mnopq' is longer than board allows.

💡 Ensure you do not skip letters or jump cells in the path.

💡 Check that word length does not exceed possible path length.

💡 Use Trie pruning to stop exploring paths longer than max word length.

Why it failed: Includes words requiring skipping or exceeding board path length. Fix by enforcing continuous adjacency and pruning by max word length.

✓ Correctly finds only valid continuous adjacency words.

t3_03corner

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

Expected["abcdefg"]

⏱ Performance - must finish in 2000ms

'abcdefg' can be formed by a valid path; 'abcfedg' requires revisiting cells or invalid moves.

💡 Check that you do not reuse cells in the same word path.

💡 Backtracking must mark visited cells and unmark after recursion.

💡 Fix by correctly managing visited state during DFS.

Why it failed: Incorrectly allows cell reuse causing invalid words to appear. Fix by proper visited marking and backtracking.

✓ Correctly prevents cell reuse and finds valid words only.

t4_01performance

Input{"_description":"n=100 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Large board and words input at upper constraint limits; solution must run in O(M * 4 * 3^(L-1)) time using Trie pruning within 2 seconds.

💡 Brute force checking each word individually will time out.

💡 Use Trie to prune search space and avoid redundant DFS.

💡 Implement in-place marking and early Trie pruning to optimize.

Why it failed: TLE due to brute force or lack of pruning. Fix by implementing Trie-based backtracking with pruning and in-place marking.

✓ Solution runs efficiently within time limits using Trie and pruning.

Practice

1. Given the following code for generating unique permutations, what is the final output when the input is [1,1,2]?

from typing import List

def permuteUnique(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        seen = set()
        for i in range(start, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

print(permuteUnique([1,1,2]))

easy

A. [[1,2,1],[1,1,2],[2,1,1]]

B. [[1,1,2],[2,1,1],[1,2,1]]

C. [[1,1,2],[1,2,1],[2,1,1]]

D. [[2,1,1],[1,1,2],[1,2,1]]

Solution

1. Step 1: Trace initial sorting and first level of recursion

   Input sorted to [1,1,2]. At start=0, i iterates over 0 to 2. First, swap nums[0] with nums[0] (1), add 1 to seen, recurse.

2. Step 2: Trace subsequent recursion and skipping duplicates

   At start=1, i iterates 1 to 2. Swap nums[1] with nums[1] (1), add 1 to seen, recurse. Then swap nums[2] with nums[1] (2), add 2 to seen, recurse. Duplicate 1 at i=2 skipped due to seen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected unique permutations in lex order [OK]

Hint: Sort input and skip duplicates with seen set [OK]

Common Mistakes:

• Misordering output permutations due to swap order

2. You need to generate all possible orderings of a list of unique integers. Which algorithmic approach guarantees that all permutations are generated without duplicates and with optimal time complexity?

easy

A. Backtracking with either a used array or in-place swapping to explore all permutations

B. Sorting the array repeatedly and collecting unique sequences

C. Dynamic programming to build permutations from smaller subproblems

D. Greedy algorithm that picks the next smallest unused element at each step

Solution

1. Step 1: Understand the problem requires all permutations

   Generating all permutations means enumerating every possible ordering of the input elements without duplicates.

2. Step 2: Identify the approach that systematically explores all orderings

   Backtracking with a used array or in-place swapping explores all permutations by recursively building sequences or swapping elements, ensuring no duplicates and covering all possibilities.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking is the standard method for generating all permutations [OK]

Hint: Backtracking systematically explores all permutations [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all permutations without duplicates

3. Consider the following snippet from an optimized Sudoku solver using backtracking with heuristics. Given the board below, what is the length of candidates for the first empty cell chosen after sorting empties by candidate count? Board: [['5', '3', '.', '.', '7', '.', '.', '.', '.'], ['6', '.', '.', '1', '9', '5', '.', '.', '.'], ['.', '9', '8', '.', '.', '.', '.', '6', '.'], ['8', '.', '.', '.', '6', '.', '.', '.', '3'], ['4', '.', '.', '8', '.', '3', '.', '.', '1'], ['7', '.', '.', '.', '2', '.', '.', '.', '6'], ['.', '6', '.', '.', '.', '.', '2', '8', '.'], ['.', '.', '.', '4', '1', '9', '.', '.', '5'], ['.', '.', '.', '.', '8', '.', '.', '7', '9']] Code snippet:

def get_candidates(r, c):
    b = (r//3)*3 + c//3
    return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
first_empty = empties[0]
candidates_len = len(get_candidates(first_empty[0], first_empty[1]))

What is the value of candidates_len?

easy

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Identify first empty cell after sorting

   Check empties and compute candidates for each; the cell with fewest candidates is chosen first.

2. Step 2: Calculate candidates for first empty cell (0,2)

   Row 0 has {'5','3','7'}, column 2 has {'8'}, box 0 has {'5','3','6','9','8'}. Candidates are digits not in any of these sets: '1','2','4'. So length is 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Counting candidates for (0,2) yields 3 [OK]

Hint: Count candidates by excluding row, column, box digits [OK]

Common Mistakes:

• Forgetting box constraints
• Miscounting candidates for first empty cell

4. Consider the following code snippet for palindrome partitioning. Which line contains a subtle bug that causes incorrect or duplicate partitions?

def partition(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start, path):
        if start == len(s):
            result.append(path)  # Line X
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

medium

A. Line 6: palindrome check misses single character substrings

B. Line X: appending path without copying causes shared references

C. Line 12: for loop range should be from start+1 to len(s)+1

D. Line 15: missing path.pop() after backtrack call

Solution

1. Step 1: Identify how results are stored

   Appending path directly stores a reference, so later modifications affect all stored results.

2. Step 2: Correct approach

   Use result.append(path[:]) to append a copy, preserving each partition snapshot.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Shared references cause incorrect final partitions [OK]

Hint: Always append a copy of path to results [OK]

Common Mistakes:

• Forgetting to copy path before appending
• Incorrect palindrome check boundaries
• Forgetting to pop after recursion

5. Examine the following code snippet for the Word Search problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

medium

A. Line where board[r][c] = temp is restored after recursion

B. Line where temp = board[r][c]

C. Line where directions are defined

D. Line missing board[r][c] = '#' to mark visited

Solution

1. Step 1: Identify missing visited marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits.

2. Step 2: Understand impact of missing marking

   Without marking, dfs can revisit the same cell multiple times, causing incorrect matches or infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Marking visited cells is essential to prevent reuse [OK]

Hint: Check if visited cells are marked before recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Restoring cell too early