Command Palette

Search for a command to run...

Hectal
Problem 13.7 · BacktrackingMedium

Word Search

PatternBacktrackingGraph DFS and Flood Fill

What it teaches: Grid backtracking: mark the cell, explore four neighbours, restore the cell.

Practise it on judges as “Word Search”.

The problem

Given an m × n grid of letters and a word, return true if the word can be spelled by moving between horizontally or vertically adjacent cells, using each cell at most once.

Example 1

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

Example 2

Input: same board, word = "ABCB"
Output: false

The B can't be reused.

Constraints

  • 1 ≤ m, n ≤ 6
  • 1 ≤ word.length ≤ 15

Pattern clues in the wording

  • → Path through a grid without reusing cells
  • → Try every start, backtrack on dead ends

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean exist(char[][] board, String word) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"
true
2
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "SEE"
true
3
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCB"
false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. DFS with in-place marking · O(m · n · 3ᴸ) for word length L
1

DFS with in-place marking

Time O(m · n · 3ᴸ) for word length L Space O(L)

dfs(r, c, i): fail if out of bounds or board[r][c] != word[i]. If i is the last index, succeed. Otherwise mark, try four directions with i + 1, restore.

Approach 1
class Solution {
    public boolean exist(char[][] board, String word) {
        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[0].length; c++)
                if (dfs(board, word, r, c, 0)) return true;
        return false;
    }

    private boolean dfs(char[][] b, String w, int r, int c, int i) {
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(i)) return false;
        if (i == w.length() - 1) return true;
        char saved = b[r][c];
        b[r][c] = '#';                                   // mark as used
        boolean found = dfs(b, w, r + 1, c, i + 1) || dfs(b, w, r - 1, c, i + 1)
                     || dfs(b, w, r, c + 1, i + 1) || dfs(b, w, r, c - 1, i + 1);
        b[r][c] = saved;                                 // restore
        return found;
    }
}

Verdict: Each step has at most 3 new directions (not back where it came from).

Before you submit

Edge cases and common mistakes

Test these inputs

  • Word longer than the number of cells
  • Single-cell board
  • Word needs a U-turn

Mistakes people make

  • Not restoring the cell.
  • Checking i == length before checking the character.

Interview

Follow-up questions

How would you find many words at once?