Word Search

MediumBacktracking Matrix DFS

In a tablet word game, players spell words by dragging a finger across a grid of letter tiles, board. A drag can start on any tile and then moves one tile at a time up, down, left or right, never diagonally, and no tile may be used twice in the same word. Uppercase and lowercase letters are different tiles.

Given board and a word, return true if the word can be spelled with a single drag, and false otherwise.

Example 1

Input: board = [["C","A","T","S"],["O","R","E","P"],["D","E","N","T"]], word = "CODE"
Output: true

Explanation: Start on the top-left C, drag down to O and D, then right to E.

Example 2

Input: board = [["C","A","T","S"],["O","R","E","P"],["D","E","N","T"]], word = "RENT"
Output: true

Explanation: From R, drag right to E, down to N and right to T.

Example 3

Input: board = [["C","A","T","S"],["O","R","E","P"],["D","E","N","T"]], word = "CARD"
Output: false

Explanation: C, A and R connect, but the only D touches R diagonally.

Constraints

The board has between 1 and 6 rows and between 1 and 6 columns.
word is between 1 and 15 characters long.
board and word contain only English letters, uppercase or lowercase.

Follow-up: How would you find every word from a large dictionary that appears on the board, without searching for each word separately?

💡 Hint 1

Try every cell as a starting point, then explore the four neighbours recursively while matching the next letter.

💡 Hint 2

Mark a cell as used while it is on the current path and unmark it when you backtrack, so other paths can still use it.

💡 Hint 3

Cheap pruning: if the board does not contain enough copies of some letter in word, the answer is false without any search.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Backtracking DFS. First count the letters on the board; if word needs more of some letter than the board has, return false straight away (this kills the worst cases, such as a board full of A and a word ending in B). Then, from every cell, run dfs(r, c, k): the cell must be on the board and equal to word[k]. Temporarily overwrite it with a marker so the path cannot reuse it, recurse into the four neighbours for k + 1, and restore the letter afterwards. Reaching k === word.length - 1 on a matching cell means the whole word was found.

Time O(m · n · 3^L) for a word of length L (each step has at most 3 new directions)Space O(L) recursion depth

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;
  if (word.length > rows * cols) return false;
  const count = new Map();
  for (const row of board) for (const ch of row) count.set(ch, (count.get(ch) ?? 0) + 1);
  for (const ch of word) {
    const left = (count.get(ch) ?? 0) - 1;
    if (left < 0) return false;
    count.set(ch, left);
  }
  const dfs = (r, c, k) => {
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[k]) return false;
    if (k === word.length - 1) return true;
    const saved = board[r][c];
    board[r][c] = '#';
    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    board[r][c] = saved;
    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;
}

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        if (word.length() > rows * cols) return false;
        int[] count = new int[128];
        for (char[] row : board) for (char ch : row) count[ch]++;
        for (char ch : word.toCharArray()) if (--count[ch] < 0) return false;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int k) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(k)) return false;
        if (k == word.length() - 1) return true;
        char saved = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r + 1, c, k + 1) || dfs(board, word, r - 1, c, k + 1)
            || dfs(board, word, r, c + 1, k + 1) || dfs(board, word, r, c - 1, k + 1);
        board[r][c] = saved;
        return found;
    }
}

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
function exist(board, word) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit