Word Search

📋

Problem

Imagine you have a crossword puzzle grid and a word list. You want to find if a particular word can be traced in the grid by moving horizontally or vertically, letter by letter.

Given a 2D board of characters and a word, determine if the word exists in the grid. The word can 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.

1 ≤ board.length ≤ 2001 ≤ board[i].length ≤ 2001 ≤ word.length ≤ 10^3board and word consist only of uppercase and lowercase English letters

Edge cases: Empty board → falseWord longer than total cells → falseWord is a single letter present in board → true

</>

IDE

def exist(board: List[List[str]], word: str) -> bool:public boolean exist(char[][] board, String word)bool exist(vector<vector<char>>& board, string word)function exist(board, word)

def exist(board, word):
    # Write your solution here
    pass

class Solution {
    public boolean exist(char[][] board, String word) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool exist(vector<vector<char>>& board, string word) {
    // Write your solution here
    return false;
}

function exist(board, word) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueAllowing diagonal moves or revisiting cells in the same path.✅ Restrict DFS to four directions (up, down, left, right) and mark visited cells properly.

Wrong: falseFailing to explore all paths due to premature pruning or incorrect backtracking.✅ Implement full backtracking exploring all directions and restore visited cells after recursion.

Wrong: trueReusing the same cell multiple times in the path violating problem constraints.✅ Mark cells as visited during recursion and restore after to prevent reuse.

Wrong: trueNot handling empty board input, causing crashes or incorrect true return.✅ Add checks for empty board or empty rows before starting DFS.

Wrong: falseNot handling single letter word or single cell board correctly.✅ Add base case to return true if word length is 1 and board cell matches.

✓

Test Cases

Now test your code on edge cases like empty boards and single letters.

Try tricky cases that expose greedy or adjacency mistakes.

Prepare for performance tests that require pruning or memoization.

t1_01basic

Input{"board":[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"word":"ABCCED"}

Expectedtrue

⏱ Performance - must finish in 2000ms

The word 'ABCCED' can be found by the path A->B->C->C->E->D in the grid.

💡 Try searching from each cell and use DFS to match the word characters.

💡 Use backtracking to mark visited cells so you don't reuse them in the same path.

💡 Mark cells as visited by temporarily changing their value and restore after recursion.

Why it failed: Failed to find the correct path or did not mark visited cells properly, causing reuse of cells or missed paths. Fix by implementing backtracking with in-place marking.

✓ Correctly finds the word using DFS and backtracking with visited marking.

t1_02basic

Input{"board":[["C","A","A"],["A","A","A"],["B","C","D"]],"word":"AAB"}

Expectedtrue

⏱ Performance - must finish in 2000ms

The word 'AAB' can be found starting at board[1][1] -> board[1][0] -> board[2][0].

💡 Check all starting positions matching the first letter.

💡 Explore all four directions recursively with backtracking.

💡 Ensure to mark visited cells to avoid revisiting in the same path.

Why it failed: Incorrectly returns false due to missing valid paths or not handling multiple adjacent same letters. Fix by exploring all directions and backtracking correctly.

✓ Correctly explores all paths and finds the word.

t2_01edge

Input{"board":[],"word":"ANY"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty board cannot contain any word.

💡 Check if the board is empty before searching.

💡 Return false immediately if board or board[0] is empty.

💡 Add a guard clause to handle empty input.

Why it failed: Code crashes or returns true on empty board input. Fix by adding checks for empty board or empty rows before DFS.

✓ Properly handles empty board and returns false.

t2_02edge

Input{"board":[["A"]],"word":"A"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single letter board matches single letter word.

💡 Check if the single cell matches the word's first character.

💡 Return true if word length is 1 and board cell matches.

💡 Ensure base case handles single letter word correctly.

Why it failed: Fails to return true for single letter word matching single cell. Fix by handling base case when word length is 1.

✓ Correctly returns true for single letter match.

t2_03edge

Input{"board":[["A","A"],["A","A"]],"word":"AAAA"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Board with all identical letters can form the word if length fits without reusing cells.

💡 Check that you do not reuse the same cell twice in the path.

💡 Backtracking must mark visited cells to avoid reuse.

💡 Ensure path length matches word length without revisiting.

Why it failed: Returns false due to incorrect visited marking or allowing reuse of cells. Fix by proper backtracking and visited marking.

✓ Correctly finds the word using all identical letters without reuse.

t3_01corner

Input{"board":[["A","B","C"],["D","E","F"],["G","H","I"]],"word":"ABF"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Word 'ABF' cannot be formed because 'F' is not adjacent to 'B'.

💡 Check adjacency strictly: only horizontal or vertical neighbors allowed.

💡 Do not allow diagonal moves in DFS.

💡 Verify neighbors carefully before recursive calls.

Why it failed: Incorrectly returns true by allowing diagonal moves. Fix by restricting DFS to four directions only (up, down, left, right).

✓ Correctly restricts moves to four directions and returns false.

t3_02corner

Input{"board":[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]],"word":"ABCESEEEFS"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Word requires careful backtracking to avoid premature pruning.

💡 Avoid greedy pruning that stops after first partial match fails.

💡 Explore all possible paths fully before backtracking.

💡 Backtracking must try all directions even if some fail early.

Why it failed: Fails by greedy pruning after partial match fails, missing valid paths. Fix by exploring all paths with full backtracking.

✓ Correctly explores all paths and finds the word.

t3_03corner

Input{"board":[["A","B","C"],["D","E","F"],["G","H","I"]],"word":"ABCDEFGHI"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Word longer than total cells or requiring reuse of cells is impossible.

💡 Check if word length exceeds total cells in board.

💡 Return false early if word length > rows * cols.

💡 Avoid revisiting cells to form longer words.

Why it failed: Incorrectly returns true by reusing cells or ignoring length constraints. Fix by adding length check and visited marking.

✓ Correctly returns false for impossible word length or reuse.

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"]],"word":"ABCDEFGHIJKLMNOPQRSTUVWX"}

Expectednull

⏱ Performance - must finish in 2000ms

Large 10x10 board with word length 24 tests O(N*3^L) complexity; must complete within 2 seconds.

💡 Brute force DFS has exponential time complexity in word length.

💡 Use pruning or memoization to improve performance.

💡 Early termination if character frequencies mismatch can help.

Why it failed: TLE due to exponential DFS without pruning. Fix by adding pruning based on character frequency or memoization.

✓ Algorithm runs within time limit confirming expected complexity.

Practice

1. Given the following code snippet, what is the final output of letterCombinations('23')?

from collections import deque

def letterCombinations(digits):
    if not digits:
        return []
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

print(letterCombinations('23'))

easy

A. ['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']

B. ['abc', 'def']

C. ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

D. ['a', 'b', 'c', 'd', 'e', 'f']

Solution

1. Step 1: Trace queue after processing digit '2'

   Initial queue: [''] Letters for '2': 'abc' After processing: ['a', 'b', 'c']

2. Step 2: Trace queue after processing digit '3'

   Letters for '3': 'def' For each prefix in ['a', 'b', 'c'], append each letter: 'a' + 'd','e','f' -> 'ad','ae','af' 'b' + 'd','e','f' -> 'bd','be','bf' 'c' + 'd','e','f' -> 'cd','ce','cf' Final queue: ['ad','ae','af','bd','be','bf','cd','ce','cf']

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected letter combinations for '23' [OK]

Hint: Queue expands combinations breadth-first per digit [OK]

Common Mistakes:

• Mixing order of combinations
• Confusing concatenation order

2. You need to count all distinct ways to place n queens on an nxn chessboard so that no two queens threaten each other. Which algorithmic approach guarantees finding all valid solutions efficiently by exploring partial placements and pruning invalid ones early?

easy

A. Backtracking that tries all column placements per row and abandons invalid partial boards

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming that stores counts of valid queen placements per row without conflict checks

D. Breadth-first search enumerating all board states level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all valid queen placements with no conflicts, which demands exploring all possibilities.

2. Step 2: Identify suitable algorithm

   Backtracking systematically tries each column per row and abandons partial solutions that violate constraints, ensuring correctness and pruning search space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid configurations efficiently [OK]

Hint: Counting all valid placements requires backtracking [OK]

Common Mistakes:

• Assuming greedy placement always works
• Believing DP without conflict checks suffices

3. You are given an array of integers and need to find the lexicographically next greater permutation of its elements. Which approach guarantees finding this next permutation in optimal time without generating all permutations?

easy

A. Scan from the end to find a pivot where the sequence stops increasing, swap with the smallest greater element on the right, then reverse the suffix.

B. Apply a greedy approach by swapping the first two elements that are out of order from the start.

C. Use dynamic programming to store all permutations and find the next one by memoization.

D. Generate all permutations, sort them, and pick the next one after the current permutation.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the lexicographically next greater permutation, which requires finding the next sequence just larger than the current one.

2. Step 2: Identify the optimal approach

   The approach scanning from the end to find a pivot where the sequence stops increasing, swapping with the smallest greater element on the right, then reversing the suffix guarantees the next permutation in O(n) time without generating all permutations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is correct but inefficient; DP and greedy do not guarantee correct next permutation [OK]

Hint: Next permutation uses pivot-swap-reverse pattern [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using greedy from start fails on suffix order

4. The following BFS code attempts to remove invalid parentheses but contains a subtle bug:

from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str):
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                # BUG: removing characters other than parentheses
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
    return res

What is the bug in this code?

medium

A. The found flag is reset inside the inner loop, causing premature termination

B. The is_valid function incorrectly returns True for unbalanced strings

C. The visited set is not updated correctly, causing duplicates

D. The code removes characters even if they are not '(' or ')', expanding search unnecessarily

Solution

1. Step 1: Identify character removal condition

   The code removes characters at every index without checking if they are '(' or ')', which is incorrect.

2. Step 2: Consequence of bug

   Removing non-parenthesis characters leads to invalid strings and unnecessary BFS states, increasing complexity and possibly missing valid results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only parentheses should be removed to prune search space [OK]

Hint: Only remove '(' or ')' characters during BFS [OK]

Common Mistakes:

• Removing all characters
• Incorrect visited updates
• Misusing found flag

5. Suppose the problem is modified so that the same letter cell can be reused multiple times in forming a single word. Which modification to the backtracking with Trie approach correctly handles this change without causing infinite loops?

hard

A. Use a memoization cache keyed by (row, col, Trie node) to avoid infinite loops.

B. Keep visited marking but reset it after each recursive call to allow reuse.

C. Remove visited marking and add a recursion depth limit equal to word length.

D. Remove visited marking and rely on Trie pruning only.

Solution

1. Step 1: Understand reuse implications

   Allowing reuse of cells means cycles can occur, causing infinite recursion without additional safeguards.

2. Step 2: Identify correct prevention method

   Memoization keyed by (row, col, Trie node) prevents revisiting the same state repeatedly, breaking cycles and infinite loops.

3. Step 3: Evaluate other options

   Removing visited marking alone causes infinite loops; depth limit is arbitrary and may miss valid paths; resetting visited marking still forbids reuse within one path.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Memoization ensures correctness with cell reuse allowed [OK]

Hint: Memoization avoids infinite loops when cells can be reused [OK]

Common Mistakes:

• Removing visited marking without cycle detection causes infinite loops.