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: Build a Trie (prefix tree) from the given words. A Trie efficiently stores and searches for prefixes of words. Each node in the Trie represents a character, and the path from the root to a leaf node represents a complete word. We'll add an end-of-word marker to each leaf node.

2. Depth-First Search (DFS): For each cell in the board, perform a DFS to explore all possible paths. The DFS function will check if the current path forms a valid prefix in the Trie.

3. Backtracking: If a path doesn't form a valid prefix or reaches a dead end, backtrack to explore other paths.

4. Word Discovery: If a leaf node (end-of-word) in the Trie is reached during DFS, add the corresponding word to the result list. Avoid duplicate words.

Explanation

The Trie optimizes the search by quickly discarding paths that don't match any words. DFS explores all possible word formations on the board. Backtracking prevents revisiting cells within a single word's construction.

Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

struct TrieNode {
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
        isEnd = false;
    }
};

void insert(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int index = c - 'a';
        if (!node->children[index]) {
            node->children[index] = new TrieNode();
        }
        node = node->children[index];
    }
    node->isEnd = true;
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    TrieNode* root = new TrieNode();
    for (const string& word : words) {
        insert(root, word);
    }

    int m = board.size();
    int n = board[0].size();
    unordered_set<string> result;
    
    function<void(int, int, TrieNode*, string)> dfs = 
        [&](int row, int col, TrieNode* node, string currentWord) {
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] == '#') return;

        char c = board[row][col];
        int index = c - 'a';
        if (!node->children[index]) return;

        currentWord += c;
        board[row][col] = '#'; // Mark as visited

        if (node->children[index]->isEnd) {
            result.insert(currentWord);
        }

        dfs(row + 1, col, node->children[index], currentWord);
        dfs(row - 1, col, node->children[index], currentWord);
        dfs(row, col + 1, node->children[index], currentWord);
        dfs(row, col - 1, node->children[index], currentWord);

        board[row][col] = c; // Backtrack: unmark
    };

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

    vector<string> resultVector(result.begin(), result.end());
    return resultVector;
}

int main() {
    vector<vector<char>> board = {
        {'o','a','a','n'},
        {'e','t','a','e'},
        {'i','h','k','r'},
        {'i','f','l','v'}
    };
    vector<string> words = {"oath","pea","eat","rain"};
    vector<string> foundWords = findWords(board, words);
    for (const string& word : foundWords) {
        cout << word << " ";
    }
    cout << endl; // Output: eat oath

    return 0;
}

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 worst case, DFS explores all possible paths. The Trie lookup is O(L).

• Space Complexity: O(W * L), where W is the number of words and L is the average length of a word (for the Trie). The space used for the result set is also proportional to the number of found words. The recursive call stack in DFS also takes space proportional to L in the worst case.