Can a Word Be Traced Through Adjacent Board Letters?

Medium20–25 min

Topics

BacktrackingRecursionMatrix

Companies

AmazonMicrosoftFacebook

Given a grid of letters and a target word, determine whether the word can be traced out by moving between horizontally or vertically adjacent cells, using each cell at most once along the path. Computing the result of continuing in each of the four directions into its own variable before combining them with OR is correct, but it means every direction gets explored even after an earlier one has already confirmed the word can be completed from here. Chaining the same four calls together in a single OR expression relies on short-circuit evaluation — standard in every mainstream language — so the moment one direction succeeds, the rest are never called at all.

Test Case 1:

Input:board = ["HAT","ELP","SOS"], word = "HELP"

Output:true

Explanation:H(0,0) → E(1,0) → L(1,1) → P(1,2) — every step moves to an adjacent, unused cell.

Test Case 2:

Input:board = ["HAT","ELP","SOS"], word = "HATS"

Output:false

Explanation:H → A → T reaches (0,2), but no 'S' is adjacent to it — every path following H-A-T dead-ends.

Test Case 3:

Input:board = ["HAT","ELP","SOS"], word = "SOS"

Output:true

Explanation:S(2,0) → O(2,1) → S(2,2) — reusing the letter 'S' is fine since it comes from two different cells.

Constraints

◆1 ≤ board.length, board[0].length ≤ 6
◆1 ≤ word.length ≤ 15
◆board and word consist of uppercase English letters
◆Each cell of the board may be used at most once per attempted path, and only horizontally/vertically adjacent cells may follow each other

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Explore All Four Directions Before Combining Results

Brute

From the current cell, compute the result of continuing down, up, right, and left — all four, into four separate variables — before combining them with OR to decide whether this cell leads to a solution. Correctness is fine, but once continuing in even one direction already confirms the word can be completed, the other three directions still get fully explored anyway, since all four results are computed before any combining happens.

TimeO(rows · cols · 4^L)

SpaceO(L)

Java

Try it out

class Solution {
    public boolean wordExistsOnBoard(String[] board, String word) {
        int n = board.length, m = board[0].length();
        boolean[][] visited = new boolean[n][m];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (dfs(board, word, r, c, 0, visited)) return true;
            }
        }
        return false;
    }

    private boolean dfs(String[] board, String word, int r, int c, int idx, boolean[][] visited) {
        if (idx == word.length()) return true;
        int n = board.length, m = board[0].length();
        if (r < 0 || r >= n || c < 0 || c >= m || visited[r][c] || board[r].charAt(c) != word.charAt(idx)) return false;
        visited[r][c] = true;
        boolean down = dfs(board, word, r + 1, c, idx + 1, visited);
        boolean up = dfs(board, word, r - 1, c, idx + 1, visited);
        boolean right = dfs(board, word, r, c + 1, idx + 1, visited);
        boolean left = dfs(board, word, r, c - 1, idx + 1, visited);
        visited[r][c] = false;
        return down || up || right || left;
    }
}

Optimal — Short-Circuit the Moment a Direction Succeeds

Optimal

Chain the four directional calls together with a single OR expression instead of computing each into its own variable first. Every language here evaluates OR left to right and stops the instant one operand is true — so as soon as one direction confirms the rest of the word can be completed, the remaining directions are never even called. Same search space, same final answer, but a direction that would have contributed nothing new is skipped entirely rather than explored and discarded.