☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

Word Search

Hard TUF ID 874 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an m x n grid of characters board and a string word. Return true if word can be spelled by walking through the grid: start at any cell, and each next letter must come from a cell that shares a side (up, down, left, right) with the previous one. A cell may be used at most once in a single spelling.

Constraints: 1 ≤ m, n ≤ 6, 1 ≤ word.length ≤ 15, all characters are letters.

Example 1

board = A B C E        word = "ABCCED"
        S F C S
        A D E E
answer = true       // (0,0) A -> (0,1) B -> (0,2) C -> (1,2) C -> (2,2) E -> (2,1) D

Example 2

board = A B C E        word = "ABCB"
        S F C S
        A D E E
answer = false      // after A, B, C the only neighbouring B is the one already used

Approach 1: Brute force, enumerate every path

Intuition. The statement defines a spelling as a path of word.length() distinct, side-adjacent cells. The most literal method is to generate every such path, read off the letters it visits, and compare that string with word. We never look at the letters while building the path; we only compare at the end.

Algorithm.

  1. For every cell (r, c) start a path there.
  2. Mark the cell used, append its letter to the current string.
  3. If the string has word.length() characters, compare it with word.
  4. Otherwise extend the path into each unused neighbour and recurse.
  5. On the way back remove the letter and unmark the cell, so sibling branches see a clean state.
static boolean bruteForce(char[][] board, String word) {
    int m = board.length, n = m == 0 ? 0 : board[0].length;
    if (word.isEmpty()) return true;
    boolean[][] used = new boolean[m][n];
    StringBuilder path = new StringBuilder();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (enumerate(board, r, c, used, path, word)) return true;
        }
    }
    return false;
}

private static boolean enumerate(char[][] board, int r, int c, boolean[][] used, StringBuilder path, String word) {
    used[r][c] = true;
    path.append(board[r][c]);
    boolean found = false;
    if (path.length() == word.length()) {
        found = path.toString().equals(word);
    } else {
        for (int d = 0; d < 4 && !found; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && !used[nr][nc]) {
                found = enumerate(board, nr, nc, used, path, word);
            }
        }
    }
    path.deleteCharAt(path.length() - 1);
    used[r][c] = false;
    return found;
}

DR and DC are the usual direction arrays {-1, 1, 0, 0} and {0, 0, -1, 1}.

Complexity. Time O(m · n · 3^L) where L = word.length(): every cell is a start, and after the first step each cell has at most three unused neighbours. Space O(m · n + L) for the used matrix and the recursion stack.

The waste is obvious: a path whose first letter is already wrong is still extended to full length. On a 6 x 6 board with a 15-letter word that is tens of millions of useless paths.

Approach 2: Better, backtrack on the first mismatch

Intuition. Compare the letters as the path grows. The cell we stand on must equal word[i]; if it does not, nothing that extends this path can ever spell the word, so return immediately. This is the classic backtracking shape: choose a neighbour, check the constraint, recurse, undo.

The i == word.length() - 1 check means “the last letter matched”, so no extra step is needed to confirm the full word.

Algorithm.

  1. For every cell whose letter equals word[0], call dfs(r, c, 0).
  2. dfs(r, c, i): if board[r][c] != word[i] return false. If i is the last index return true.
  3. Mark (r, c) used, try dfs on each in-bounds unused neighbour with i + 1; if any returns true, unmark and return true.
  4. Unmark (r, c) and return false.
static boolean better(char[][] board, String word) {
    int m = board.length, n = m == 0 ? 0 : board[0].length;
    if (word.isEmpty()) return true;
    boolean[][] used = new boolean[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (board[r][c] == word.charAt(0) && dfsVisited(board, r, c, 0, word, used)) return true;
        }
    }
    return false;
}

private static boolean dfsVisited(char[][] board, int r, int c, int i, String word, boolean[][] used) {
    if (board[r][c] != word.charAt(i)) return false;
    if (i == word.length() - 1) return true;
    used[r][c] = true;
    for (int d = 0; d < 4; d++) {
        int nr = r + DR[d], nc = c + DC[d];
        if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && !used[nr][nc]
                && dfsVisited(board, nr, nc, i + 1, word, used)) {
            used[r][c] = false;
            return true;
        }
    }
    used[r][c] = false;
    return false;
}

Complexity. Time O(m · n · 3^L) in the worst case, but the bound is only reached on adversarial boards such as a grid full of a with the word aaaa...ab; on typical input most branches die within a step or two. Space O(m · n + L).

Why the undo matters: used is shared by every branch. If a failed branch left cells marked, a later branch starting elsewhere would be forbidden from using them and could miss a real spelling.

Approach 3: Optimal, in-place marking and pruning

Intuition. Two refinements keep the same search but shrink it.

First, the used matrix is redundant. Overwriting the current cell with a sentinel such as # (a character that never appears in word) makes the mismatch test board[r][c] != word[i] reject that cell automatically. Restore the letter on the way back. This removes the extra matrix and the bounds check becomes the first line of the recursion, which shortens the code.

Second, two cheap global checks: if the word needs more copies of some letter than the board contains, the answer is false without any search. And because a path can be read in either direction, we may search for the reversed word; starting from the end whose letter is rarer on the board means fewer starting cells and earlier dead ends. The classic adversarial case aaaa...ab on an all-a board becomes a search for baaa...a, which fails instantly because no cell holds b.

Algorithm.

  1. If word is longer than m · n, return false.
  2. Count letters of the board and of the word; if any wordCount[ch] > boardCount[ch], return false.
  3. If the first letter of word is more common on the board than the last, reverse word.
  4. From every cell run dfsInPlace(r, c, 0), which marks with # and restores.
static boolean optimal(char[][] board, String word) {
    int m = board.length, n = m == 0 ? 0 : board[0].length;
    if (word.isEmpty()) return true;
    if (word.length() > m * n) return false;
    int[] boardCount = new int[128], wordCount = new int[128];
    for (char[] row : board) for (char ch : row) boardCount[ch]++;
    for (int i = 0; i < word.length(); i++) wordCount[word.charAt(i)]++;
    for (int ch = 0; ch < 128; ch++) if (wordCount[ch] > boardCount[ch]) return false;
    // Start from the end whose letter is rarer on the board: fewer starting cells and earlier dead ends.
    if (boardCount[word.charAt(0)] > boardCount[word.charAt(word.length() - 1)]) {
        word = new StringBuilder(word).reverse().toString();
    }
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (dfsInPlace(board, r, c, 0, word)) return true;
        }
    }
    return false;
}

private static boolean dfsInPlace(char[][] board, int r, int c, int i, String word) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
    if (board[r][c] != word.charAt(i)) return false;
    if (i == word.length() - 1) return true;
    char saved = board[r][c];
    board[r][c] = '#';                               // mark as used; '#' never equals a letter of the word
    boolean found = dfsInPlace(board, r - 1, c, i + 1, word) || dfsInPlace(board, r + 1, c, i + 1, word)
            || dfsInPlace(board, r, c - 1, i + 1, word) || dfsInPlace(board, r, c + 1, i + 1, word);
    board[r][c] = saved;                             // undo the mark on the way back
    return found;
}

Dry run on Example 1, word = "ABCCED". A appears twice on the board and D once, so the search actually runs on "DECCBA" starting at the only D:

step cell letter needed match?
0 (2,1) D yes, mark #
1 (2,2) E yes (neighbours (1,1) F and (2,0) A fail first)
2 (1,2) C yes
3 (0,2) C yes
4 (0,1) B yes
5 (0,0) A yes, last index: return true

Every marked cell is restored as the recursion unwinds, so the caller sees the original board.

Complexity. Time O(m · n · 3^L) worst case; the pruning does not change the bound but removes the pathological inputs that actually reach it. Space O(L) for the recursion stack plus two 128-entry arrays; no visited matrix.

Edge cases and pitfalls