Problem

Given a 2D matrix of characters, determine whether a given word exists in the grid when you may move in any of the 8 directions (up, down, left, right and the 4 diagonals). If the word exists, return the visit-order matrix (an m x n integer matrix where each used cell contains its 1-based step index); if the word is not found, return an empty matrix. When multiple valid paths exist, returning any one valid path is acceptable.

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|c|} \hline A & B & C & E \\ \hline \colorbox{YellowOrange} S & \colorbox{YellowOrange} F & C & S \\ \hline \colorbox{YellowOrange} A & D & \colorbox{YellowOrange} E & E \\ \hline \end{array}

\implies \Huge \begin{array}{|c|c|c|c|} \hline 0 & 0 & 0 & 0 \\ \hline 1 & 3 & 0 & 0 \\ \hline 2 & 0 & 4 & 0 \\ \hline \end{array} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

Output:
0 0 0 0
1 3 0 0
2 0 4 0
Explanation: The printed solution matrix above shows the visit order (1-based) of the path that spells "SAFE":
start at `S` at (1,0) -> `A` at (2,0) -> `F` at (1,1) -> `E` at (2,2). Zeros indicate unused cells.

Example 2

$$ \Huge \begin{array}{|c|c|c|c|} \hline \colorbox{YellowOrange} k & \colorbox{YellowOrange} 5 & x & c \\ \hline a & \colorbox{YellowOrange} k & 5 & k \\ \hline \colorbox{YellowOrange} c & x & k & x \\ \hline x & c & x & x \\ \hline \end{array}

\implies

\Huge \begin{array}{|c|c|c|c|} \hline 1 & 2 & 0 & 0 \\ \hline 0 & 3 & 0 & 0 \\ \hline 4 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline \end{array} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input:
board = [
  ["k","5","x","c"],
  ["a","k","5","k"],
  ["c","x","k","x"],
  ["x","c","x","x"]
], word = "k5kc"

Output:
0 1 0 4
0 2 3 0
0 0 0 0
0 0 0 0
Explanation: One valid 8-directional path that spells "k5kc" is:
start at `k` at (0,0) -> `5` at (0,1) -> `k` at (1,1) -> `c` at (2,0). The ASCII and LaTeX matrices above show the visit-order (1-based); zeros are unused cells.

Example 3

1
2
3
4
5
6
7
8

Input:
board = [
  ["a","b","c"],
  ["d","e","f"],
  ["g","h","i"]
], word = "xyz"
Output: []
Explanation: The word "xyz" cannot be formed in any 8-directional path in the board; the function returns an empty matrix to indicate failure.
Similar Problems

Solution

Method 1 - Backtracking (8-direction, print path)

Intuition

This is a standard DFS/backtracking problem; allowing 8-direction moves only enlarges the neighbor set. We search from every cell and track visited cells. To print the path, we record the visit order in a solution matrix and undo the marks on backtrack.

Approach

  1. Create a solution matrix of the same dimensions as board, initialized to zeros. Use a step counter starting at 1.
  2. Try each cell in the board as a starting point.
  3. From a cell, perform DFS: if the current character matches word[idx] and the cell is unused, set solution[r][c] = step and increment step.
  4. If idx == len(word) - 1 the full word is matched: return the current solution matrix (which contains 1-based visit indices).
  5. Otherwise, recurse into all 8 neighbors (dx,dy pairs). If any recursion returns true, propagate true upwards.
  6. If none succeed, undo the mark (solution[r][c] = 0 and decrement step) and continue searching other starts.
  7. If all starts fail, return false.

State Definition

  • solution[r][c] — integer step index (1-based) when cell (r,c) is used in the current candidate path; 0 means unused.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
 public:
  // Returns the visit-order matrix (m x n) if a path is found; otherwise returns an empty matrix.
  std::vector<std::vector<int>> exist(std::vector<std::vector<char>>& board, const std::string& word) {
    if (board.empty() || board[0].empty() || word.empty()) return {};
    int m = board.size(), n = board[0].size();
    std::vector<std::vector<int>> sol(m, std::vector<int>(n, 0));
    int step = 1;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (dfs(board, word, i, j, 0, sol, step)) {
          return sol;
        }
      }
    }
    return {};
  }

 private:
  const std::vector<std::pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};

  bool inbounds(int r, int c, int m, int n) { return r >= 0 && c >= 0 && r < m && c < n; }

  bool dfs(std::vector<std::vector<char>>& b, const std::string& w, int r, int c, int idx,
           std::vector<std::vector<int>>& sol, int& step) {
    int m = b.size(), n = b[0].size();
    if (!inbounds(r,c,m,n) || sol[r][c] != 0 || b[r][c] != w[idx]) return false;
    sol[r][c] = step++;
    if (idx == static_cast<int>(w.size()) - 1) return true;
    for (auto [dr, dc] : dirs) {
      if (dfs(b, w, r + dr, c + dc, idx + 1, sol, step)) return true;
    }
    sol[r][c] = 0; --step;
    return false;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
  private final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};

  // Returns an m x n visit-order matrix if found, otherwise returns an empty matrix (0-length first dimension).
  public int[][] exist(char[][] board, String word) {
    if (board == null || board.length == 0 || word == null || word.length() == 0) return new int[0][0];
    int m = board.length, n = board[0].length;
    int[][] sol = new int[m][n];
    int[] step = new int[]{1};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (dfs(board, word, i, j, 0, sol, step)) {
          return sol;
        }
      }
    }
    return new int[0][0];
  }

  private boolean inbounds(int r, int c, int m, int n) { return r >= 0 && c >= 0 && r < m && c < n; }

  private boolean dfs(char[][] b, String w, int r, int c, int idx, int[][] sol, int[] step) {
    int m = b.length, n = b[0].length;
    if (!inbounds(r,c,m,n) || sol[r][c] != 0 || b[r][c] != w.charAt(idx)) return false;
    sol[r][c] = step[0]++;
    if (idx == w.length() - 1) return true;
    for (int[] d : DIRS) {
      if (dfs(b, w, r + d[0], c + d[1], idx + 1, sol, step)) return true;
    }
    sol[r][c] = 0; step[0]--;
    return false;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from typing import List

class Solution:
  def exist(self, board: List[List[str]], word: str) -> List[List[int]]:
    if not board or not board[0] or not word:
      return []
    m, n = len(board), len(board[0])
    sol = [[0]*n for _ in range(m)]
    dirs = [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]

    def inb(r: int, c: int) -> bool:
      return 0 <= r < m and 0 <= c < n

    def dfs(r: int, c: int, idx: int, step_ref: List[int]) -> bool:
      if not inb(r,c) or sol[r][c] != 0 or board[r][c] != word[idx]:
        return False
      sol[r][c] = step_ref[0]
      step_ref[0] += 1
      if idx == len(word) - 1:
        return True
      for dr, dc in dirs:
        if dfs(r + dr, c + dc, idx + 1, step_ref):
          return True
      sol[r][c] = 0
      step_ref[0] -= 1
      return False

    for i in range(m):
      for j in range(n):
        if dfs(i, j, 0, [1]):
          return sol
    return []

Complexity

  • ⏰ Time complexity: O(m * n * 8^L) – Let m x n be board dimensions and L the word length. From each start we may explore up to 8 neighbors per character, yielding 8^L possibilities; repeated for m*n starting cells.
  • 🧺 Space complexity: O(L + m * n) – recursion stack O(L) plus solution matrix O(m*n) used for printing the path.