Word Search | Problems

You're given an m x n character grid board and a target string word. Return true if word can be traced out by moving through the grid one letter at a time, stepping only to a horizontally or vertically neighboring cell at each move, and never reusing a cell already visited within that same path.

Input Format

Implement exist(board, word). Inputs below show JavaScript function arguments; there is no stdin parsing.

Output Format

Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"

Output

true

Example 2

Input

board = [["A","B"]]
word = "ABA"

Output

false

Constraints

1 <= m, n <= 6
1 <= word.length <= 15
board and word consist of lowercase and uppercase English letters

Test Cases (2)

Case 1

Args: [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"ABCCED"] Expected: true

Case 2

Args: [[["A","B"]],"ABA"] Expected: false

Topics

Array Two Pointers

Iterate through each cell in the grid. If it matches the first character of the word, run DFS to match remaining characters. Mark cells as visited during recursion and restore them on backtrack.

javascript

function exist(board, word) {
  const rows = board.length, cols = board[0].length;

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[idx]) return false;

    const temp = board[r][c];
    board[r][c] = '#';

    const found = dfs(r + 1, c, idx + 1) || dfs(r - 1, c, idx + 1) ||
                  dfs(r, c + 1, idx + 1) || dfs(r, c - 1, idx + 1);

    board[r][c] = temp;
    return found;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Time: O(m·n·3^L) where L is the word length Space: O(L) recursion depth

Saved in this browser only. Private to you.