Word Search

Word Search is a grid puzzle that interviewers love. You get a board of letters. You have to find a word by walking from cell to cell. The catch is you can only move up, down, left, or right, and you cannot reuse a cell. This is backtracking on a grid, and it teaches you how to mark a path and then clean it up.

🎯 The Problem

You get a grid of letters and a word. You must find out if the word exists in the grid as a walk.

• A walk is a chain of neighbor cells with no repeats.
• Neighbors are the cells directly up, down, left, and right.
• You cannot move diagonally.
• You cannot use the same cell twice in one path.
• For the word ABCCED: start at A, go right to B, right to C, down to C, down to E, left to D.
• Each step is a neighbor and no cell repeats, so the answer is true.

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

Explanation: A -> B -> C -> C -> E -> D forms the word
by moving between neighboring cells without reusing any cell.

Here is the grid with the path for ABCCED shown step by step. Each arrow moves to a neighbor cell.

🐢 Approach 1: DFS With a Separate Visited Grid (Brute Force)

The idea in one line: search from every cell, and track used cells in a second grid.

The idea:

• Try starting the word from every cell in the grid.
• Follow one path as far as it matches, letter by letter.
• Keep a separate boolean grid that marks which cells the current path uses.

How it works:

• Before stepping onto a cell, check the visited grid so the path never reuses it.
• Mark the cell visited, search the four neighbors, then unmark it on the way back.

Why it is weak:

• It allocates a whole extra grid the same size as the board.
• It reads and writes that grid on every step.
• The logic is fine, but the extra memory is wasted when the board itself can hold the mark.

Here is the separate-visited-grid code:

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(row, col, index, visited):
        if index == len(word):
            return True
        if row < 0 or col < 0 or row == rows or col == cols:
            return False
        if (row, col) in visited or board[row][col] != word[index]:
            return False

        visited.add((row, col))
        found = (
            dfs(row + 1, col, index + 1, visited)
            or dfs(row - 1, col, index + 1, visited)
            or dfs(row, col + 1, index + 1, visited)
            or dfs(row, col - 1, index + 1, visited)
        )
        visited.remove((row, col))
        return found

    return any(dfs(r, c, 0, set()) for r in range(rows) for c in range(cols))

⚡ Approach 2: DFS With In-Place Mark and Restore (Best)

The idea in one line: mark a used cell right inside the board, then restore it after the neighbors.

The idea:

• DFS means depth first search, following one path as far as it goes before trying another.
• Match one letter at a time against the current letter of the word.
• Use the board cell itself to remember “this cell is in the current path”.

How it works:

• If the cell is off the grid or the letter does not match, this path fails right away.
• If it matches and it was the last letter, the whole word is found.
• Save the cell’s letter, then change it to a marker like a hash sign.
• Search the four neighbors for the next letter.
• Restore the original letter after the neighbors return.

Why it is fast:

• No extra grid is needed, since the board carries the mark.
• The marker can never match a real word letter, so a path cannot step back onto itself.
• Mark, search the neighbors, then unmark. That is the whole rhythm.

Steps to Solve

1. Loop over every cell in the grid as a possible start.
2. From a start cell, run a depth first search that tracks which letter you are matching.
3. If the cell is out of bounds, or does not match the current letter, this path fails.
4. If it matches and it was the last letter, the word is found.
5. Mark the current cell as used so it is not reused in this path.
6. Search all four neighbors for the next letter.
7. Restore the cell’s letter after the neighbors return, then move on.

Here is the DFS decision tree from the starting A. Each branch is one neighbor we try. A wrong letter ends that branch.

#include <stdio.h>
#include <string.h>

int rows = 3, cols = 4;
char board[3][5] = {
    "ABCE",
    "SFCS",
    "ADEE"
};
char word[] = "ABCCED";

int dfs(int r, int c, int index) {
    if (index == (int)strlen(word)) return 1;       // matched all letters
    if (r < 0 || c < 0 || r >= rows || c >= cols) return 0;  // off the grid
    if (board[r][c] != word[index]) return 0;        // letter mismatch

    char saved = board[r][c];
    board[r][c] = '#';                               // mark as used

    int found = dfs(r + 1, c, index + 1) ||          // down
                dfs(r - 1, c, index + 1) ||          // up
                dfs(r, c + 1, index + 1) ||          // right
                dfs(r, c - 1, index + 1);            // left

    board[r][c] = saved;                             // restore (backtrack)
    return found;
}

int main(void) {
    int exists = 0;
    for (int r = 0; r < rows && !exists; r++)
        for (int c = 0; c < cols && !exists; c++)
            if (dfs(r, c, 0)) exists = 1;
    printf("%s\n", exists ? "true" : "false");
    return 0;
}

true

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

vector<string> board = {"ABCE", "SFCS", "ADEE"};
string word = "ABCCED";

bool dfs(int r, int c, int index) {
    if (index == (int)word.size()) return true;      // matched everything
    if (r < 0 || c < 0 || r >= (int)board.size() ||
        c >= (int)board[0].size()) return false;     // off the grid
    if (board[r][c] != word[index]) return false;    // mismatch

    char saved = board[r][c];
    board[r][c] = '#';                               // mark used

    bool 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] = saved;                             // restore (backtrack)
    return found;
}

int main() {
    bool exists = false;
    for (int r = 0; r < (int)board.size() && !exists; r++)
        for (int c = 0; c < (int)board[0].size() && !exists; c++)
            if (dfs(r, c, 0)) exists = true;
    cout << (exists ? "true" : "false") << endl;
    return 0;
}

true

public class WordSearch {
    static char[][] board = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };
    static String word = "ABCCED";

    static boolean dfs(int r, int c, int index) {
        if (index == word.length()) return true;     // matched all letters
        if (r < 0 || c < 0 || r >= board.length ||
            c >= board[0].length) return false;       // off the grid
        if (board[r][c] != word.charAt(index)) return false;  // mismatch

        char saved = board[r][c];
        board[r][c] = '#';                            // mark used

        boolean 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] = saved;                          // restore (backtrack)
        return found;
    }

    public static void main(String[] args) {
        boolean exists = false;
        for (int r = 0; r < board.length && !exists; r++)
            for (int c = 0; c < board[0].length && !exists; c++)
                if (dfs(r, c, 0)) exists = true;
        System.out.println(exists);
    }
}

true

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, index):
        if index == len(word):            # matched every letter
            return True
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return False                  # walked off the grid
        if board[r][c] != word[index]:    # letter does not match
            return False

        saved = board[r][c]
        board[r][c] = "#"                 # mark this cell as used

        found = (dfs(r + 1, c, index + 1) or   # down
                 dfs(r - 1, c, index + 1) or   # up
                 dfs(r, c + 1, index + 1) or   # right
                 dfs(r, c - 1, index + 1))     # left

        board[r][c] = saved               # restore (backtrack)
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False


board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
]
print(exist(board, "ABCCED"))

True

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r, c, index) {
    if (index === word.length) return true;   // matched every letter
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false; // off grid
    if (board[r][c] !== word[index]) return false;  // mismatch

    const saved = board[r][c];
    board[r][c] = "#";                         // mark used

    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] = saved;                       // restore (backtrack)
    return found;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

const board = [
  ["A", "B", "C", "E"],
  ["S", "F", "C", "S"],
  ["A", "D", "E", "E"],
];
console.log(exist(board, "ABCCED"));

true

Let us read the Python version line by line. The mark and restore steps are the heart of grid backtracking.

rows, cols = len(board), len(board[0]) reads the grid size once. We use these to check when a move walks off the edge.

if index == len(word): is the success base case. index is which letter of the word we are trying to match. When index reaches the word length, every letter matched in order. So the word is found and we return True.

if r < 0 or c < 0 or r >= rows or c >= cols: is the boundary check. If the row or column is outside the grid, we cannot stand there. So this path fails with False.

if board[r][c] != word[index]: checks the letter. If the current cell does not hold the letter we need, this path is wrong. We stop and return False.

saved = board[r][c] remembers the original letter. Then board[r][c] = "#" marks the cell as used. The hash sign can never match a real word letter. So no neighbor search can step back onto this cell during the same path.

The four dfs calls explore the neighbors. They try down, up, right, and left, each looking for the next letter at index + 1. The or means we stop as soon as any direction finds the word.

board[r][c] = saved is the backtrack. It puts the original letter back. So the cell is free again for any other path. Without this restore, one failed path would block cells forever.

⏱️ Time and Space Complexity

Let the grid have m times n cells. From each cell we branch into four directions, and the path can be as long as the word, call its length L. So the search from one start is about 4 to the power of L. We try every cell as a start, so the total time is O(m × n × 4ᴸ). The space is O(L) for the recursion depth, since the deepest path equals the word length.

🧩 Key Takeaways

• ✅ Try every cell as a possible start for the word.
• ✅ Match one letter at a time, moving only up, down, left, or right.
• ✅ Mark the current cell as used so one path never reuses a cell.
• ✅ Restore the cell after exploring its neighbors, so other paths stay free.
• ✅ The success base case is when the letter index reaches the word length.

🚀 What’s Next?

• N-Queens
• Letter Combinations of a Phone Number