Solving Word Search II: Finding Words on a Board

The "Word Search II" problem involves searching for all possible words from a given list within a grid of letters. This task requires efficiently traversing the grid and checking for the presence of words.

Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example

Consider a board and a list of words:

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"]

Input:

((board = [
  ["a", "b"],
  ["c", "d"],
]),
  (words = ["abcb"]));

Output:

[]

Solution Approach - Trie and Backtracking

class TrieNode {
  children: Map<string, TrieNode>;
  word: string | null;

  constructor() {
    this.children = new Map();
    this.word = null;
  }
}

class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.word = word; // Store word at the leaf
  }
}

function findWords(board: string[][], words: string[]): string[] {
  const trie = new Trie();
  for (const word of words) {
    trie.insert(word);
  }

  const foundWords: string[] = [];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      dfs(board, i, j, trie.root, foundWords);
    }
  }

  function dfs(board: string[][], i: number, j: number, node: TrieNode, result: string[]) {
    const char = board[i][j];
    if (!node.children.has(char)) return;

    const nextNode = node.children.get(char);
    if (nextNode!.word) {
      // Found a word
      result.push(nextNode!.word);
      nextNode!.word = null; // Avoid duplicate entries
    }

    board[i][j] = "#"; // Mark as visited
    const directions = [
      [0, 1],
      [1, 0],
      [0, -1],
      [-1, 0],
    ]; // Right, Down, Left, Up
    for (const [dx, dy] of directions) {
      const x = i + dx,
        y = j + dy;
      if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
        dfs(board, x, y, nextNode!, result);
      }
    }
    board[i][j] = char; // Reset
  }

  return foundWords;
}

Breaking Down the Solution

• Trie for Word Storage: Store the list of words in a Trie for efficient searching.
• Backtracking for Grid Traversal: Use depth-first search (DFS) with backtracking to explore the board.
• Finding Words: On each step of DFS, check if the current path corresponds to a word in the Trie.

Conclusion

Word Search II is a challenging problem that combines Trie data structures with backtracking techniques, demonstrating advanced concepts in algorithm design and optimization.