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. You are given a string containing parentheses and letters. The goal is to remove the minimum number of parentheses to make the string valid (balanced parentheses) and return all possible results. Which algorithmic approach guarantees finding all valid strings with the minimum removals efficiently?

easy

A. Greedy approach that removes invalid parentheses from left to right without backtracking

B. Dynamic Programming that counts valid substrings and reconstructs solutions

C. Breadth-First Search (BFS) that explores all strings by removing one parenthesis at a time level-by-level

D. Brute force generating all subsequences and checking validity

Solution

1. Step 1: Understand problem constraints

   The problem requires minimal removals and all valid results, so partial or greedy removal may miss some minimal solutions.

2. Step 2: Analyze BFS approach

   BFS explores all strings by removing one parenthesis at a time, level-by-level, ensuring the first valid strings found have minimal removals and all such strings are collected.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS guarantees minimal removals and completeness [OK]

Hint: Minimal removals require level-by-level BFS [OK]

Common Mistakes:

• Greedy misses some minimal solutions
• Brute force is correct but inefficient
• DP doesn't apply directly here

2. What is the time complexity of the optimal backtracking solution that generates all valid parentheses sequences for input n?

medium

A. O(2^{2n} * n) because it generates all sequences and checks validity

B. O(n^2) because it builds sequences of length 2n with nested loops

C. O(n!) because it permutes parentheses positions

D. O(\frac{4^n}{n^{3/2}}) because the number of valid sequences is the nth Catalan number

Solution

1. Step 1: Identify number of valid sequences

   The number of valid parentheses sequences is the nth Catalan number, approximately 4^n / (n^{3/2}).

2. Step 2: Analyze backtracking time

   Backtracking generates all valid sequences, so time is proportional to number of sequences times sequence length, which is O(4^n / n^{3/2} * n) = O(4^n / n^{1/2}).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches known Catalan number growth for valid parentheses [OK]

Hint: Catalan number growth dominates complexity [OK]

Common Mistakes:

• Confusing brute force with backtracking complexity
• Assuming factorial complexity

3. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?

medium

A. O(n) because it scans the array a constant number of times

B. O(n log n) because it sorts the suffix after the pivot

C. O(n!) due to generating all permutations

D. O(n^2) because it swaps elements multiple times in nested loops

Solution

1. Step 1: Identify the main operations

   The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).

2. Step 2: Sum up the operations

   All steps are linear scans or swaps, so total time complexity is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No sorting or factorial generation involved, linear scans only [OK]

Hint: Next permutation scans array linearly multiple times [OK]

Common Mistakes:

• Confusing suffix reversal with sorting
• Assuming factorial due to permutations

4. What is the time complexity of the optimal factorial-based algorithm to find the k-th permutation of n numbers, and why?

medium

A. O(n^2) because each of the n iterations involves removing an element from a list of size up to n.

B. O(n!) because it generates all permutations internally.

C. O(n log n) due to sorting operations inside the algorithm.

D. O(n) because factorial computations and indexing are constant time per iteration.

Solution

1. Step 1: Analyze the main loop

   The algorithm runs a loop n times to select each digit of the permutation.

2. Step 2: Consider list removal cost

   Removing an element from the numbers list is O(n) in worst case, so total is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each iteration's pop is linear, leading to quadratic time [OK]

Hint: List pop at arbitrary index costs O(n), not O(1) [OK]

Common Mistakes:

• Assuming factorial computations dominate time
• Thinking it's O(n) due to fixed loop count
• Confusing factorial precomputation with sorting

5. Consider the following buggy code snippet for restoring IP addresses. Which line contains the subtle bug that causes invalid IP addresses to be included?

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            # Bug: Missing check for leading zeros
            if length == 3 and int(segment) > 255:
                continue
            stack.append((start + length, path + [segment]))
    return res

medium

A. Line missing check for segments with leading zeros

B. Line checking if segment length is 3 and value > 255

C. Line pruning based on remaining characters and segments

D. Line appending new segment to stack

Solution

1. Step 1: Identify missing validation

   The code lacks a check to reject segments with leading zeros like '00' or '01', which are invalid.

2. Step 2: Confirm other checks are correct

   Check for segment > 255 and pruning are present and correct; appending to stack is correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check allows invalid IP segments [OK]

Hint: Leading zero check is mandatory to avoid invalid IPs [OK]

Common Mistakes:

• Forgetting leading zero validation
• Misplacing pruning conditions