Problem statement

You are given a grid of letters as board, one string per row, and a string word.

Return true if word can be spelled out by a path of horizontally or vertically adjacent cells, where no cell is used more than once in the path.

Example 1

Input: board = ["abce","sfcs","adee"], word = "abcced"
Output: true

Example 2

Input: board = ["abce","sfcs","adee"], word = "see"
Output: true

Example 3

Input: board = ["abce","sfcs","adee"], word = "abcb"
Output: false
Explanation: The b cannot be reused.

Constraints

• 1 <= board.length <= 4
• All rows have the same length, between 1 and 4.
• 1 <= word.length <= 6
• board and word consist of lowercase English letters.

Hints for Word Search

1. Hint 1

   Try starting the match at every cell and grow it one letter at a time.

2. Hint 2

   Mark a cell as used before recursing and unmark it afterwards — that is the backtracking step.

3. Hint 3

   Bail out as soon as the current letter does not match; that pruning is what keeps the search tractable.

How to solve Word Search

Backtracking: try every start cell, extend the match to an adjacent unused cell whose letter matches the next character, and unmark on return.

Approach

1. search(r, c, index) returns true when index == len(word).
2. Fail fast on out-of-bounds, used, or mismatched letter.
3. Mark used, recurse in four directions, unmark.

Why it works

The recursion explores every simple path spelling the word's prefix; the immediate letter check prunes almost all branches.

Complexity

• Time — O(m · n · 3^L)
• Space — O(L) recursion

Pitfalls

• Forgetting to unmark a cell after the recursion returns blocks other paths.

Reference solution

Python

def exist(board, word: str) -> bool:
    rows, cols = len(board), len(board[0])
    used = [[False] * cols for _ in range(rows)]

    def search(r, c, index):
        if index == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols):
            return False
        if used[r][c] or board[r][c] != word[index]:
            return False
        used[r][c] = True
        found = (search(r + 1, c, index + 1) or search(r - 1, c, index + 1)
                 or search(r, c + 1, index + 1) or search(r, c - 1, index + 1))
        used[r][c] = False
        return found

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

Java

private static boolean searchWord(String[] board, String word, boolean[][] used, int r, int c, int index) {
    if (index == word.length()) return true;
    int rows = board.length, cols = board[0].length();
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (used[r][c] || board[r].charAt(c) != word.charAt(index)) return false;
    used[r][c] = true;
    boolean found = searchWord(board, word, used, r + 1, c, index + 1)
            || searchWord(board, word, used, r - 1, c, index + 1)
            || searchWord(board, word, used, r, c + 1, index + 1)
            || searchWord(board, word, used, r, c - 1, index + 1);
    used[r][c] = false;
    return found;
}

public static boolean exist(String[] board, String word) {
    int rows = board.length, cols = board[0].length();
    boolean[][] used = new boolean[rows][cols];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (searchWord(board, word, used, r, c, 0)) return true;
        }
    }
    return false;
}

C++

static bool searchWord(vector<string>& board, const string& word, vector<vector<bool>>& used, int r, int c, int index) {
    if (index == (int) word.size()) return true;
    int rows = (int) board.size(), cols = (int) board[0].size();
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (used[r][c] || board[r][c] != word[index]) return false;
    used[r][c] = true;
    bool found = searchWord(board, word, used, r + 1, c, index + 1)
        || searchWord(board, word, used, r - 1, c, index + 1)
        || searchWord(board, word, used, r, c + 1, index + 1)
        || searchWord(board, word, used, r, c - 1, index + 1);
    used[r][c] = false;
    return found;
}

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

JavaScript

var exist = function(board, word) {
    const rows = board.length, cols = board[0].length;
    const used = [];
    for (let r = 0; r < rows; r++) {
        const row = [];
        for (let c = 0; c < cols; c++) row.push(false);
        used.push(row);
    }
    const search = function(r, c, index) {
        if (index === word.length) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (used[r][c] || board[r].charAt(c) !== word.charAt(index)) return false;
        used[r][c] = true;
        const found = search(r + 1, c, index + 1) || search(r - 1, c, index + 1) ||
            search(r, c + 1, index + 1) || search(r, c - 1, index + 1);
        used[r][c] = false;
        return found;
    };
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (search(r, c, 0)) return true;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium