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. Consider the following Python code implementing Heap's algorithm for permutations:

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums[:])
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

print(permute([1,2,3]))

What is the value of the variable res after the algorithm completes?

easy

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

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

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

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

Solution

1. Step 1: Trace initial state and first swaps

   Start with [1,2,3], res = [[1,2,3]]. For i=1 (odd), swap nums[c[1]] and nums[1], c[1]=0, swap nums[0] and nums[1] -> [2,1,3], append to res.

2. Step 2: Continue iterations and record permutations

   Following Heap's algorithm, the permutations generated in order are: [1,2,3], [2,1,3], [3,1,2], [1,3,2], [3,2,1], [2,3,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches Heap's algorithm output order for n=3 [OK]

Hint: Heap's algorithm generates permutations in a specific swap order [OK]

Common Mistakes:

• Confusing swap indices or order of permutations generated

2. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?

medium

A. O(n * 4^n) because we process each digit and expand combinations exponentially

B. O(2^n) because each digit doubles the number of combinations

C. O(4^n * n) because there are up to 4^n combinations and each combination is built with n concatenations

D. O(n^2) because we process n digits and each combination takes n steps

Solution

1. Step 1: Identify number of combinations

   Each digit maps to up to 4 letters, so total combinations are up to 4^n.

2. Step 2: Analyze work per combination

   Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.

3. Step 3: Simplify complexity expression

   O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Time is exponential in n with linear cost per combination [OK]

Hint: Exponential combinations times linear build cost [OK]

Common Mistakes:

• Confusing exponential base (2 vs 4)
• Ignoring concatenation cost per combination

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

4. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

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

Common Mistakes:

• Forgetting to copy before appending results in duplicate references

5. What is the time complexity of the BFS approach for removing invalid parentheses from a string of length n, considering the worst case?

medium

A. O(n * 2^n) because there can be up to 2^n states and each validity check takes O(n)

B. O(n!) because permutations of removals are explored

C. O(2^n) because BFS explores all subsets of characters without repeated checks

D. O(n^2) because each level removes one character and checks validity in O(n)

Solution

1. Step 1: Count possible states

   Each character can be either removed or kept, so up to 2^n possible strings can be generated.

2. Step 2: Analyze per-state cost

   Each string requires an O(n) validity check, so total worst-case time is O(n * 2^n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   2^n states times O(n) validity checks [OK]

Hint: 2^n states times O(n) validity checks [OK]

Common Mistakes:

• Confusing O(n^2) with BFS complexity
• Ignoring validity check cost
• Assuming factorial complexity