Word Search II Hard 0 attempts
LeetCode ↗

Word Search II

Hard BacktrackingRecursion LeetCode

You're given an m x n character board and a list of candidate strings words. Return every word from the list that can be traced out on the board by moving one letter at a time to a horizontally or vertically neighboring cell, without reusing any single cell more than once within that word's path.

Input Format
Implement findWords(board, words). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
Output
["eat","oath"]

Example 2

Input
board = [["a","a"]]
words = ["a","aa","aaa"]
Output
["a","aa"]
Constraints
  • 1 <= m, n <= 12
  • 1 <= words.length <= 3 * 10^4
  • 1 <= words[i].length <= 10
Test Cases (2)
Case 1
Args: [[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],["oath","pea","eat","rain"]] Expected: ["eat","oath"]
Case 2
Args: [[["a","a"]],["a","aa","aaa"]] Expected: ["a","aa"]
Topics
BacktrackingRecursion

Build a Trie from the word list, then DFS from every cell on the board. Traverse the Trie simultaneously — when a Trie node marks a complete word, add it to results. Prune branches to avoid redundant searches.

javascript
function findWords(board, words) {
  const root = {};
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.word = word;
  }

  const rows = board.length, cols = board[0].length;
  const result = [];

  function dfs(r, c, node) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (ch === '#' || !node[ch]) return;

    node = node[ch];
    if (node.word) {
      result.push(node.word);
      node.word = null;
    }

    board[r][c] = '#';
    dfs(r + 1, c, node);
    dfs(r - 1, c, node);
    dfs(r, c + 1, node);
    dfs(r, c - 1, node);
    board[r][c] = ch;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      dfs(r, c, root);
    }
  }
  return result;
}

Time: O(m·n·4·3^(L-1)) where L is max word length Space: O(total characters in all words) for the Trie

Saved in this browser only. Private to you.

JavaScript