Word Search | Problems

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where horizontal or vertical neighbors are adjacent. The same letter cell may not be used more than once.

Sample Input

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

Sample Output

true

Constraints

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

Test Cases

Case 1

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

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.

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.