Word Search

mediumBacktracking84 stepsJava · Python · C++

Does the word exist as a path of adjacent cells, using each cell at most once? Try every starting cell. DFS matches one letter at a time, temporarily marking the cell as used, and unmarks it on the way back.

▶ Watch the animated trace

Traced input: board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCCED → true. Original problem: neetcode.io/problems/search-for-word

Complexity

BestO(m·n)

AverageO(m·n·3^L)

WorstO(m·n·3^L)

SpaceO(L)

L = word length. Each step has at most 3 new directions.

Key idea

A cell can be reused in a different path, but not twice in the same path.
Mark in place (e.g. '#') instead of a separate visited array.
Restore the letter after exploring: that's the backtracking step.
Stop as soon as one path matches.

Common mistakes

Forgetting to restore the cell.
Checking index == word.length() after the bounds check instead of before.

Solution

Java

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

boolean match(char[][] b, String word, int k, int r, int c) {
    if (k == word.length()) return true;
    if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != word.charAt(k)) return false;
    char saved = b[r][c];
    b[r][c] = '#';
    boolean found = match(b, word, k + 1, r + 1, c) || match(b, word, k + 1, r - 1, c)
        || match(b, word, k + 1, r, c + 1) || match(b, word, k + 1, r, c - 1);
    b[r][c] = saved;
    return found;
}

Python

def exist(board: List[List[str]], word: str) -> bool:
    m, n = len(board), len(board[0])

    def match(k: int, r: int, c: int) -> bool:
        if k == len(word): return True
        if r < 0 or c < 0 or r >= m or c >= n or board[r][c] != word[k]: return False
        saved = board[r][c]
        board[r][c] = '#'
        found = (match(k + 1, r + 1, c) or match(k + 1, r - 1, c)
                 or match(k + 1, r, c + 1) or match(k + 1, r, c - 1))
        board[r][c] = saved
        return found

    return any(match(0, r, c) for r in range(m) for c in range(n))

C++

bool match(vector<vector<char>>& b, const string& word, int k, int r, int c) {
    if (k == (int)word.size()) return true;
    if (r < 0 || c < 0 || r >= (int)b.size() || c >= (int)b[0].size() || b[r][c] != word[k]) return false;
    char saved = b[r][c];
    b[r][c] = '#';
    bool found = match(b, word, k + 1, r + 1, c) || match(b, word, k + 1, r - 1, c)
        || match(b, word, k + 1, r, c + 1) || match(b, word, k + 1, r, c - 1);
    b[r][c] = saved;
    return found;
}

bool exist(vector<vector<char>>& board, string word) {
    for (int r = 0; r < (int)board.size(); r++)
        for (int c = 0; c < (int)board[0].size(); c++)
            if (match(board, word, 0, r, c)) return true;
    return false;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Reusing a cell The only B can't be used twice.	`board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCB`	`false`
Single cell Match on the first cell.	`board = [[a]], word = a`	`true`
Word longer than the board There's no 'c'.	`board = [[a, b]], word = abc`	`false`