Word Search

🎯

Word Search

mediumBACKTRACKINGAmazonFacebookGoogle

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.

💡 This problem is about searching for a sequence of characters in a 2D grid by exploring all possible paths. Beginners often struggle because it requires careful backtracking and marking visited cells to avoid revisiting and infinite loops.

📋

Problem Statement

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

💡

Example

Input"board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCCED'"

Outputtrue

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

Input"board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'SEE'"

Outputtrue

The word 'SEE' can be found by the path S->E->E.

Input"board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCB'"

Outputfalse

The word 'ABCB' cannot be found because the letter 'B' cannot be reused.

• Empty board → false
• Word longer than total cells → false
• Word is a single letter present in board → true
• Board with all identical letters and word repeating that letter → true if length fits

⚠️

Common Mistakes

Not marking visited cells properly

Leads to revisiting cells and infinite recursion or incorrect matches

✅ Mark cells as visited before recursion and restore after (backtracking)

Not checking boundary conditions before accessing board

Causes index out of bounds runtime errors

✅ Always check row and column indices before accessing board cells

Trying to reuse the same cell multiple times in one path

Incorrectly finds words that are not valid according to problem rules

✅ Use visited marking to prevent reusing cells in the current path

Not returning early when word is found

Unnecessary exploration leads to timeouts

✅ Return true immediately when all characters matched

Modifying the board permanently without restoring

Subsequent searches fail due to corrupted board state

✅ Restore the board cell after backtracking

🧠

Brute Force (Pure Recursion with Backtracking)

💡 This approach is the foundation for understanding the problem. It tries every possible path starting from each cell, which is simple but inefficient.

Intuition

Try to find the word starting from every cell. For each cell, recursively explore its neighbors to match the next character, marking cells visited to avoid reuse.

Algorithm

1. For each cell in the grid, start a DFS if the cell matches the first character of the word.
2. In DFS, check if the current cell matches the current character in the word.
3. Mark the cell as visited to avoid revisiting in the current path.
4. Recursively explore all 4 directions (up, down, left, right) for the next character.
5. If all characters are matched, return true; else backtrack and unmark the cell.

💡 The challenge is to carefully manage visited cells and backtrack correctly to explore all paths without repetition.

</>

Code

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        
        def dfs(r, c, index):
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
                return False
            temp = board[r][c]
            board[r][c] = '#'
            found = (dfs(r+1, c, index+1) or dfs(r-1, c, index+1) or
                     dfs(r, c+1, index+1) or dfs(r, c-1, index+1))
            board[r][c] = temp
            return found
        
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        return False

# Example usage:
# sol = Solution()
# print(sol.exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED'))  # True

Line Notes

def exist(self, board: List[List[str]], word: str) -> bool:Defines the main function with board and word inputs

rows, cols = len(board), len(board[0])Store dimensions to avoid repeated calls

def dfs(r, c, index):Helper function to perform DFS from cell (r,c) matching word[index]

if index == len(word):Base case: all characters matched successfully

if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:Boundary and character mismatch check

temp = board[r][c]Save current cell character before marking visited

board[r][c] = '#'Mark cell as visited to avoid reuse in current path

found = (dfs(r+1, c, index+1) or dfs(r-1, c, index+1) or dfs(r, c+1, index+1) or dfs(r, c-1, index+1))Explore all 4 directions recursively

board[r][c] = tempRestore cell after exploring all paths (backtracking)

for i in range(rows):Try starting DFS from every cell in the grid

if board[i][j] == word[0] and dfs(i, j, 0):Start DFS only if first character matches

public class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int index) {
        if (index == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index))
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r + 1, c, index + 1) ||
                        dfs(board, word, r - 1, c, index + 1) ||
                        dfs(board, word, r, c + 1, index + 1) ||
                        dfs(board, word, r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    //     System.out.println(sol.exist(board, "ABCCED")); // true
    // }
}

Line Notes

public boolean exist(char[][] board, String word)Main method signature for the problem

for (int i = 0; i < rows; i++)Iterate over each row to start DFS

if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0))Start DFS only if first character matches

private boolean dfs(char[][] board, String word, int r, int c, int index)DFS helper to explore paths

if (index == word.length()) return true;Base case: all characters matched

if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) return false;Boundary and mismatch check

char temp = board[r][c];Save current cell before marking visited

board[r][c] = '#';Mark cell visited to avoid reuse

boolean found = dfs(...) || dfs(...) || dfs(...) || dfs(...)Explore all 4 directions recursively

board[r][c] = temp;Restore cell after recursion (backtracking)

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0] && dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int index) {
        if (index == word.size()) return true;
        if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[index])
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        bool found = dfs(board, word, r + 1, c, index + 1) ||
                     dfs(board, word, r - 1, c, index + 1) ||
                     dfs(board, word, r, c + 1, index + 1) ||
                     dfs(board, word, r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<char>> board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
//     bool res = sol.exist(board, "ABCCED");
//     return 0;
// }

Line Notes

bool exist(vector<vector<char>>& board, string word)Main function signature

for (int i = 0; i < rows; i++)Loop over rows to start DFS

if (board[i][j] == word[0] && dfs(board, word, i, j, 0))Start DFS only if first character matches

bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int index)DFS helper function

if (index == word.size()) return true;Base case: all characters matched

if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[index]) return false;Boundary and mismatch check

char temp = board[r][c];Save current cell before marking visited

board[r][c] = '#';Mark cell visited to avoid reuse

bool found = dfs(...) || dfs(...) || dfs(...) || dfs(...)Explore all 4 directions recursively

board[r][c] = temp;Restore cell after recursion (backtracking)

var exist = function(board, word) {
    const rows = board.length, cols = board[0].length;
    
    function dfs(r, c, index) {
        if (index === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) return false;
        const temp = board[r][c];
        board[r][c] = '#';
        const found = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === word[0] && dfs(i, j, 0)) return true;
        }
    }
    return false;
};

// Example usage:
// console.log(exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED')); // true

Line Notes

var exist = function(board, word)Main function declaration

const rows = board.length, cols = board[0].length;Store board dimensions

function dfs(r, c, index)DFS helper function to explore paths

if (index === word.length) return true;Base case: all characters matched

if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) return false;Boundary and mismatch check

const temp = board[r][c];Save current cell before marking visited

board[r][c] = '#';Mark cell visited to avoid reuse

const found = dfs(...) || dfs(...) || dfs(...) || dfs(...)Explore all 4 directions recursively

board[r][c] = temp;Restore cell after recursion (backtracking)

for (let i = 0; i < rows; i++)Try starting DFS from every cell

⏱

Complexity

TimeO(N * 3^L) where N is number of cells and L is length of the word

SpaceO(L) recursion stack for the word length

From each cell, we explore up to 4 directions but avoid going back, so roughly 3 directions per step for L steps, repeated for each cell

💡 For a 10x10 board and word length 5, this could mean up to 100 * 3^5 = 24300 operations, which is feasible but grows quickly.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is slow for large boards or long words, so we need to optimize.

🧠

Backtracking with Early Pruning Using Character Frequency

💡 This approach improves brute force by quickly rejecting impossible searches based on character counts, reducing unnecessary DFS calls.

Intuition

Before searching, count characters in the board and the word. If the board lacks enough occurrences of any character, return false immediately.

Algorithm

1. Count frequency of each character in the board and in the word.
2. If any character in the word appears more times than in the board, return false immediately.
3. Otherwise, perform the same DFS backtracking as brute force.
4. Optionally, reverse the word if the last character is rarer than the first to reduce search space.

💡 This pruning step can save a lot of time by avoiding DFS when the word is impossible to form.

</>

Code

from typing import List
from collections import Counter

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        board_count = Counter(c for row in board for c in row)
        word_count = Counter(word)
        for c in word_count:
            if word_count[c] > board_count.get(c, 0):
                return False
        # Optional: reverse word if last char rarer than first
        if board_count[word[0]] > board_count[word[-1]]:
            word = word[::-1]
        
        def dfs(r, c, index):
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
                return False
            temp = board[r][c]
            board[r][c] = '#'
            found = (dfs(r+1, c, index+1) or dfs(r-1, c, index+1) or
                     dfs(r, c+1, index+1) or dfs(r, c-1, index+1))
            board[r][c] = temp
            return found
        
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        return False

# Example usage:
# sol = Solution()
# print(sol.exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED'))  # True

Line Notes

board_count = Counter(c for row in board for c in row)Count all characters in the board

word_count = Counter(word)Count characters in the word

for c in word_count:Check if board has enough of each character

if word_count[c] > board_count.get(c, 0):If board lacks characters, return false early

if board_count[word[0]] > board_count[word[-1]]:Heuristic to reverse word if last char is rarer

def dfs(r, c, index):DFS helper function same as brute force

temp = board[r][c]Save cell before marking visited

board[r][c] = '#'Mark visited

found = (dfs(...) or ... )Explore all 4 directions

board[r][c] = tempBacktrack by restoring cell

import java.util.*;

public class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        Map<Character, Integer> boardCount = new HashMap<>();
        for (char[] row : board) {
            for (char c : row) {
                boardCount.put(c, boardCount.getOrDefault(c, 0) + 1);
            }
        }
        Map<Character, Integer> wordCount = new HashMap<>();
        for (char c : word.toCharArray()) {
            wordCount.put(c, wordCount.getOrDefault(c, 0) + 1);
        }
        for (char c : wordCount.keySet()) {
            if (wordCount.get(c) > boardCount.getOrDefault(c, 0)) return false;
        }
        if (boardCount.get(word.charAt(0)) > boardCount.get(word.charAt(word.length() - 1))) {
            word = new StringBuilder(word).reverse().toString();
        }
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int index) {
        if (index == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index))
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r + 1, c, index + 1) ||
                        dfs(board, word, r - 1, c, index + 1) ||
                        dfs(board, word, r, c + 1, index + 1) ||
                        dfs(board, word, r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    //     System.out.println(sol.exist(board, "ABCCED")); // true
    // }
}

Line Notes

Map<Character, Integer> boardCount = new HashMap<>();Count characters in board

for (char c : word.toCharArray())Count characters in word

if (wordCount.get(c) > boardCount.getOrDefault(c, 0)) return false;Early pruning if board lacks chars

if (boardCount.get(word.charAt(0)) > boardCount.get(word.charAt(word.length() - 1)))Heuristic to reverse word

private boolean dfs(char[][] board, String word, int r, int c, int index)DFS helper same as brute force

char temp = board[r][c];Save cell before marking visited

board[r][c] = '#';Mark visited

boolean found = dfs(...) || ...Explore all 4 directions

board[r][c] = temp;Backtrack by restoring cell

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        unordered_map<char, int> boardCount, wordCount;
        for (auto& row : board) {
            for (char c : row) boardCount[c]++;
        }
        for (char c : word) wordCount[c]++;
        for (auto& p : wordCount) {
            if (boardCount[p.first] < p.second) return false;
        }
        if (boardCount[word[0]] > boardCount[word.back()]) {
            reverse(word.begin(), word.end());
        }
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0] && dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int index) {
        if (index == (int)word.size()) return true;
        if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[index])
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        bool found = dfs(board, word, r + 1, c, index + 1) ||
                     dfs(board, word, r - 1, c, index + 1) ||
                     dfs(board, word, r, c + 1, index + 1) ||
                     dfs(board, word, r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<char>> board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
//     bool res = sol.exist(board, "ABCCED");
//     return 0;
// }

Line Notes

unordered_map<char, int> boardCount, wordCount;Count characters in board and word

for (auto& p : wordCount)Check if board has enough characters

if (boardCount[word[0]] > boardCount[word.back()])Heuristic to reverse word

bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int index)DFS helper same as brute force

char temp = board[r][c];Save cell before marking visited

board[r][c] = '#';Mark visited

bool found = dfs(...) || ...Explore all 4 directions

board[r][c] = temp;Backtrack by restoring cell

var exist = function(board, word) {
    const rows = board.length, cols = board[0].length;
    const boardCount = {};
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            boardCount[board[r][c]] = (boardCount[board[r][c]] || 0) + 1;
        }
    }
    const wordCount = {};
    for (const ch of word) {
        wordCount[ch] = (wordCount[ch] || 0) + 1;
    }
    for (const ch in wordCount) {
        if (!boardCount[ch] || wordCount[ch] > boardCount[ch]) return false;
    }
    if (boardCount[word[0]] > boardCount[word[word.length - 1]]) {
        word = word.split('').reverse().join('');
    }
    
    function dfs(r, c, index) {
        if (index === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) return false;
        const temp = board[r][c];
        board[r][c] = '#';
        const found = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === word[0] && dfs(i, j, 0)) return true;
        }
    }
    return false;
};

// Example usage:
// console.log(exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED')); // true

Line Notes

const boardCount = {};Count characters in board

const wordCount = {};Count characters in word

if (!boardCount[ch] || wordCount[ch] > boardCount[ch]) return false;Early pruning if board lacks chars

if (boardCount[word[0]] > boardCount[word[word.length - 1]])Heuristic to reverse word

function dfs(r, c, index)DFS helper same as brute force

const temp = board[r][c];Save cell before marking visited

board[r][c] = '#';Mark visited

const found = dfs(...) || ...Explore all 4 directions

board[r][c] = temp;Backtrack by restoring cell

⏱

Complexity

TimeStill O(N * 3^L) but often faster due to pruning

SpaceO(L) recursion stack

Pruning avoids many DFS calls when word characters are missing or insufficient in the board

💡 This optimization can drastically reduce runtime on impossible cases, making it practical for larger inputs.

Interview Verdict: Accepted and faster than brute force on many inputs

This approach is a practical improvement and often sufficient in interviews.

🧠

Backtracking with In-Place Marking and Direction Array

💡 This approach cleans up the code by using a directions array to reduce repetition and marks visited cells in-place for space efficiency.

Intuition

Use a fixed array of direction vectors to explore neighbors, making the code concise and less error-prone.

Algorithm

1. Initialize a directions array with vectors for up, down, left, right.
2. For each cell matching the first character, start DFS.
3. In DFS, mark the cell visited by replacing its character with a sentinel.
4. Explore neighbors using the directions array.
5. Backtrack by restoring the original character.

💡 This approach is functionally similar to brute force but improves code clarity and reduces bugs.

</>

Code

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        
        def dfs(r, c, index):
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
                return False
            temp = board[r][c]
            board[r][c] = '#'
            for dr, dc in directions:
                if dfs(r + dr, c + dc, index + 1):
                    board[r][c] = temp
                    return True
            board[r][c] = temp
            return False
        
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        return False

# Example usage:
# sol = Solution()
# print(sol.exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED'))  # True

Line Notes

directions = [(1,0), (-1,0), (0,1), (0,-1)]Predefined moves for neighbors to avoid repetition

def dfs(r, c, index):DFS helper function

if index == len(word):Base case: all characters matched

for dr, dc in directions:Loop over all four directions

board[r][c] = '#'Mark cell visited

board[r][c] = tempRestore cell after recursion (backtracking)

if dfs(r + dr, c + dc, index + 1):Return early if path found

public class Solution {
    private final int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int index) {
        if (index == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index))
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        for (int[] d : directions) {
            if (dfs(board, word, r + d[0], c + d[1], index + 1)) {
                board[r][c] = temp;
                return true;
            }
        }
        board[r][c] = temp;
        return false;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    //     System.out.println(sol.exist(board, "ABCCED")); // true
    // }
}

Line Notes

private final int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};Store directions to avoid code duplication

for (int[] d : directions)Iterate over all four directions

char temp = board[r][c];Save current cell before marking visited

board[r][c] = '#';Mark cell visited

if (dfs(board, word, r + d[0], c + d[1], index + 1))Return early if path found

board[r][c] = temp;Restore cell after recursion

#include <vector>
#include <string>
using namespace std;

class Solution {
    const vector<pair<int,int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0] && dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int index) {
        if (index == (int)word.size()) return true;
        if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[index])
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        for (auto& d : directions) {
            if (dfs(board, word, r + d.first, c + d.second, index + 1)) {
                board[r][c] = temp;
                return true;
            }
        }
        board[r][c] = temp;
        return false;
    }

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<char>> board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
//     bool res = sol.exist(board, "ABCCED");
//     return 0;
// }

Line Notes

const vector<pair<int,int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};Predefined directions for neighbors

for (auto& d : directions)Loop over all directions

char temp = board[r][c];Save cell before marking visited

board[r][c] = '#';Mark visited

if (dfs(board, word, r + d.first, c + d.second, index + 1))Return early if path found

board[r][c] = temp;Restore cell after recursion

var exist = function(board, word) {
    const rows = board.length, cols = board[0].length;
    const directions = [[1,0], [-1,0], [0,1], [0,-1]];
    
    function dfs(r, c, index) {
        if (index === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) return false;
        const temp = board[r][c];
        board[r][c] = '#';
        for (const [dr, dc] of directions) {
            if (dfs(r + dr, c + dc, index + 1)) {
                board[r][c] = temp;
                return true;
            }
        }
        board[r][c] = temp;
        return false;
    }
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === word[0] && dfs(i, j, 0)) return true;
        }
    }
    return false;
};

// Example usage:
// console.log(exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED')); // true

Line Notes

const directions = [[1,0], [-1,0], [0,1], [0,-1]];Store directions to avoid code duplication

for (const [dr, dc] of directions)Iterate over all four directions

const temp = board[r][c];Save cell before marking visited

board[r][c] = '#';Mark cell visited

if (dfs(r + dr, c + dc, index + 1))Return early if path found

board[r][c] = temp;Restore cell after recursion

⏱

Complexity

TimeO(N * 3^L) same as brute force

SpaceO(L) recursion stack

Using directions array does not change complexity but improves code clarity and reduces bugs

💡 This is the preferred way to implement backtracking in interviews for readability and maintainability.

Interview Verdict: Accepted and clean code

This approach is recommended for interviews due to clarity and correctness.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 3 is recommended for interviews due to clarity and efficiency. Approach 2 is useful for optimization. Approach 1 is good for initial understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(N * 3^L)	O(L)	Yes (deep recursion possible)	N/A	Mention only - never code
2. Backtracking with Early Pruning	O(N * 3^L) but faster in practice	O(L)	Yes	N/A	Mention as optimization
3. Backtracking with Directions Array	O(N * 3^L)	O(L)	Yes	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain brute force, optimize, and finally write clean code.

How to Present

Clarify input constraints and ask about board size and character set.State the brute force backtracking approach and its complexity.Discuss pruning optimizations and how to improve runtime.Explain how to write clean code using direction arrays and in-place marking.Write code carefully and test with edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to implement backtracking correctly, handle edge cases, optimize search, and write clean, bug-free code.

Common Follow-ups

• How to find all words from a list in the board? → Use Trie + backtracking
• What if diagonal moves are allowed? → Add diagonal directions to the directions array

💡 These follow-ups test your ability to extend the solution and adapt to variations.

🔍

Pattern Recognition

When to Use

1) You have a grid or matrix input, 2) You need to find a path or sequence, 3) Movement is restricted to neighbors, 4) You must avoid revisiting cells.

Signature Phrases

word can be constructed from letters of sequentially adjacent cellsthe same letter cell may not be used more than once

NOT This Pattern When

Problems that allow revisiting cells freely or do not require path constraints (e.g., flood fill) are different.

Similar Problems

Word Search II - find multiple words using Trie + backtrackingSudoku Solver - backtracking on grid with constraintsN-Queens - backtracking with constraint satisfaction

Practice

1. Consider the following Python code snippet implementing the optimal backtracking approach for Expression Add Operators. Given input num = "123" and target = 6, what is the content of the result list after the function completes?

from typing import List

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            if i != index and num[index] == '0':
                break
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

easy

A. ["1+23", "12+3"]

B. ["123"]

C. ["1+2+3", "123"]

D. ["1+2+3"]

Solution

1. Step 1: Trace backtracking calls for num="123", target=6

   At index=0, path starts with "1". Then at index=1, add '+' and "2", evaluated=3. Then at index=2, add '+' and "3", evaluated=6, matches target, so "1+2+3" is added.

2. Step 2: Check other possible expressions

   "123" alone evaluates to 123, not 6. "1+23"=24, "12+3"=15, none equal 6. So only "1+2+3" is in result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only "1+2+3" sums to 6 [OK]

Hint: Only "1+2+3" equals 6 with given operators [OK]

Common Mistakes:

• Assuming "123" or "1+23" equals target

2. You need to place n queens on an nxn chessboard so that no two queens threaten each other (no two queens share the same row, column, or diagonal). Which algorithmic approach guarantees finding all valid solutions efficiently by pruning invalid partial placements early?

easy

A. Backtracking with pruning to avoid columns and diagonals already attacked

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

C. Dynamic programming to count valid queen placements using subproblems

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

Solution

1. Step 1: Understand problem constraints

   The problem requires placing queens so none attack each other, which involves checking columns and diagonals.

2. Step 2: Identify algorithm that prunes invalid states early

   Backtracking with pruning efficiently avoids exploring invalid partial solutions by tracking attacked columns and diagonals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking prunes invalid states early [OK]

Hint: Pruning columns and diagonals is key to efficient search [OK]

Common Mistakes:

• Thinking greedy placement always works
• Assuming DP applies directly
• Confusing BFS with pruning

3. You are given a 2D grid of letters and a list of words. You need to find all words that can be formed by sequentially adjacent letters (horizontally or vertically) without reusing the same cell in a single word. Which algorithmic approach best guarantees an efficient solution for this problem?

easy

A. Use dynamic programming to store subproblems of partial word matches.

B. Use a greedy search that picks the next letter with the highest frequency in the grid.

C. Use backtracking combined with a Trie data structure to prune invalid prefixes early.

D. Search each word independently using DFS without any prefix pruning.

Solution

1. Step 1: Understand problem constraints

   The problem requires searching multiple words in a grid with adjacency and no reuse constraints, which is expensive if done naively.

2. Step 2: Identify efficient pruning technique

   Backtracking with a Trie allows pruning search paths early when no word prefix matches, avoiding redundant searches.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie pruning reduces search space drastically compared to naive DFS [OK]

Hint: Trie + backtracking prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking greedy or DP alone can solve adjacency constraints efficiently.

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

5. Examine the following snippet from an optimized Sudoku solver. Which line contains a subtle bug that can cause incorrect solutions or failure to backtrack properly?

def backtrack():
    if not empties:
        return True
    empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
    r, c = empties[0]
    for ch in get_candidates(r, c):
        board[r][c] = ch
        rows[r].add(ch)
        cols[c].add(ch)
        boxes[(r//3)*3 + c//3].add(ch)
        empties.pop(0)
        if backtrack():
            return True
        # Undo changes
        board[r][c] = '.'
        rows[r].remove(ch)
        cols[c].remove(ch)
        boxes[(r//3)*3 + c//3].remove(ch)
        empties.insert(0, (r, c))
    return False

medium

A. Line that pops the first empty cell from empties

B. Line that sorts empties by candidate count

C. Line that adds ch to rows[r]

D. Line that resets board[r][c] to '.' after backtracking

Solution

1. Step 1: Identify mutation of empties list

   The line popping empties[0] removes the cell but is never restored on backtrack failure.

2. Step 2: Consequence of missing restoration

   Without re-adding the cell to empties after failed recursion, future calls miss this cell, causing incorrect state and solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking requires undoing all changes including empties list [OK]

Hint: Backtracking must undo all state changes, including empties list [OK]

Common Mistakes:

• Forgetting to restore empties after pop
• Assuming board reset is sufficient