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 connected. 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: We'll use a Trie (prefix tree) to efficiently store and search for the words. A Trie allows us to quickly check if a prefix exists within the set of words.

2. Trie Construction: Build a Trie from the given words. Each node in the Trie will represent a character, and each path from the root to a leaf node represents a word. We'll mark leaf nodes to indicate the end of a word.

3. Depth-First Search (DFS): Perform a DFS on the board. For each cell, we'll explore all possible paths starting from that cell.

4. Trie Traversal: During DFS, as we explore each cell, we'll simultaneously traverse the Trie. If a character is found in the Trie, we continue the search. If we reach a leaf node in the Trie, we've found a word, so we add it to our results (making sure to avoid duplicates).

5. Backtracking: After exploring a cell, we must backtrack to explore other paths. This is crucial to ensure we don't use the same cell more than once in a word.

6. Result: The DFS will systematically explore all possible paths in the board, checking each path against the Trie. The function will return a list of all found words.

Explanation

The solution uses a Trie to optimize the search for words. Building the Trie allows for efficient prefix checking. The DFS systematically explores all paths, leveraging the Trie to quickly determine if a prefix (and ultimately a word) exists. Backtracking is essential to ensure that all possible word combinations are explored while adhering to the constraints of the problem.

Code

using System;
using System.Collections.Generic;

public class Solution {
    private class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public bool isWordEnd = false;
    }

    public IList<string> FindWords(char[][] board, string[] words) {
        IList<string> result = new List<string>();
        TrieNode root = BuildTrie(words);

        int m = board.Length;
        int n = board[0].Length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                DFS(board, i, j, root, "", result);
            }
        }

        return result;
    }

    private TrieNode BuildTrie(string[] words) {
        TrieNode root = new TrieNode();
        foreach (string word in words) {
            TrieNode node = root;
            foreach (char c in word) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.isWordEnd = true;
        }
        return root;
    }

    private void DFS(char[][] board, int i, int j, TrieNode node, string word, IList<string> result) {
        int m = board.Length;
        int n = board[0].Length;

        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == '#') return;

        char c = board[i][j];
        int index = c - 'a';

        if (node.children[index] == null) return;

        node = node.children[index];
        word += c;

        if (node.isWordEnd) {
            result.Add(word);
            node.isWordEnd = false; // Avoid duplicates
        }

        char temp = board[i][j];
        board[i][j] = '#'; // Mark as visited

        DFS(board, i + 1, j, node, word, result);
        DFS(board, i - 1, j, node, word, result);
        DFS(board, i, j + 1, node, word, result);
        DFS(board, i, j - 1, node, word, result);

        board[i][j] = temp; // Backtrack
    }
}

Complexity

• Time Complexity: O(M * N * 4^L), where M and N are the dimensions of the board, and L is the maximum length of a word in the words list. The 4^L factor comes from the branching factor of the DFS (4 directions). Trie operations are considered O(1) on average.

• Space Complexity: O(W + M * N), where W is the sum of the lengths of all words in words (for the Trie), and M * N is the space used by the board (in the worst case, we might have to store all board cells as visited).