Crack the Backend

Problem Statement

Given a 2D board of characters and a string word, return true if word exists in the grid. The word can be constructed from letters of adjacent cells (horizontal or vertical; not diagonal), where each cell is used at most once. Same letter cell may not be used more than once.

We try every cell (i, j) as the starting position. From there we DFS: at each step we must match word[index] with board[r][c]; we mark the cell as visited, recurse on 4 neighbors, then unmark (backtrack) so other paths can use it.

Key Observations

Backtracking: For each starting cell (i, j), DFS with (r, c, index): if index == word.length() we've matched the whole word — return true. If (r, c) is out of bounds or board[r][c] != word.charAt(index), return false. Mark board[r][c] as visited (e.g. temporarily change to a non-letter); recurse on 4 neighbors with index+1; unmark (restore the character). Return true if any recursion returns true.
We must restore the cell after recursion so that a different path (from another start or branch) can use it.

Approach

High-level: For each (i, j), run DFS(i, j, 0). In DFS(r, c, index): if index == word.length return true; if out of bounds or board[r][c] != word[index] return false; mark board[r][c]; for each of 4 neighbors if DFS(neighbor, index+1) return true; unmark; return false.

Steps: Double loop (i,j). In DFS: if index==len return true. If invalid cell or char mismatch return false. Save board[r][c], set to '#' (or use visited set). Recurse 4 dirs. Restore board[r][c]. Return true if any recurse true.

Implementation

Java

public boolean exist(char[][] board, String word) {

    for (int i = 0; i < board.length; i++)
    for (int j = 0; j < board[0].length; j++)
    if (dfs(board, word, i, j, 0)) {
        return true;
    }

    return false;
}

boolean dfs(char[][] b, String w, int i, int j, int idx) {

    if (idx == w.length()) {
        return true;
    }

    if (i<0||i>=b.length||j<0||j>=b[0].length||b[i][j]!=w.charAt(idx)) {
        return false;
    }

    char t = b[i][j]; b[i][j] = '#';
    boolean found = dfs(b,w,i+1,j,idx+1)||dfs(b,w,i-1,j,idx+1)||dfs(b,w,i,j+1,idx+1)||dfs(b,w,i,j-1,idx+1);
    b[i][j] = t;
    return found;
}

Test Cases

Example 1

Input

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

Expected

true

Explanation

Path exists.

Complexity Analysis

Time: O(mn4^len).
Space: O(len).

Follow-ups

Word Search II: multiple words; use trie.