Word Search II hard

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 1:

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","b"],["c","d"]], words = ["abcb"] Output: []

Steps:

1. Trie Data Structure: Build a Trie (prefix tree) from the given words. A Trie efficiently stores and searches for prefixes of words. Each node in the Trie will represent a character, and it will have pointers to its children. We'll mark the end of a valid word in the Trie.

2. Depth-First Search (DFS): For each cell in the board, perform a Depth-First Search (DFS). The DFS explores adjacent cells to find words.

3. DFS Exploration:

   • During the DFS, we build up the current word by traversing the Trie.
   • We check if the current character exists as a child of the current Trie node. If it does, we continue the search recursively.
   • If we reach the end of a word in the Trie, we add it to the results.
   • We mark the current cell as visited to prevent cycles and reuse of characters. After exploring, we backtrack by unmarking the cell.

4. Result: After exploring all cells and words, we return the list of found words.

Explanation:

The Trie significantly optimizes the search. Instead of repeatedly searching the entire board for each word, we efficiently check prefixes as we explore. The DFS systematically explores all possible word formations on the board. The use of a visited set within the DFS prevents revisiting the same cell during a search, ensuring we find only valid words.

Code:

class TrieNode {
    children: { [char: string]: TrieNode } = {};
    isWord: boolean = false;
}

function findWords(board: string[][], words: string[]): string[] {
    const root = new TrieNode();
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isWord = true;
    }

    const result: string[] = [];
    const rows = board.length;
    const cols = board[0].length;
    const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));

    const dfs = (row: number, col: number, node: TrieNode, word: string) => {
        if (row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col]) {
            return;
        }

        const char = board[row][col];
        if (!node.children[char]) {
            return;
        }

        word += char;
        visited[row][col] = true;
        if (node.children[char].isWord) {
            result.push(word);
            node.children[char].isWord = false; // Avoid duplicates
        }

        dfs(row + 1, col, node.children[char], word);
        dfs(row - 1, col, node.children[char], word);
        dfs(row, col + 1, node.children[char], word);
        dfs(row, col - 1, node.children[char], word);

        visited[row][col] = false; // Backtrack
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            dfs(i, j, root, "");
        }
    }

    return result;
}

Complexity:

• Time Complexity: O(MN4^L) where M and N are the dimensions of the board, and L is the maximum length of the words. In the worst case, the DFS might explore all possible paths. The Trie lookups are relatively fast (O(L) on average).

• Space Complexity: O(N*M + sum of word lengths). This accounts for the space used by the board, the visited matrix, and the Trie. The Trie's space depends on the total number of characters in the input words.