Word Search II

HardTries

Given a grid of letters and a list of words, return all words that can be formed from sequentially adjacent cells without reusing a cell.

Open problem

Constraints

1 <= m, n <= 12
1 <= words.length <= 3 * 10^4

Trie plus grid DFS

Time O(m * n * 4^L)Space O(total word length)

Insert all words into a trie, then DFS from each cell following trie links so many words are searched at once. Mark found words and prune visited cells with a temporary marker.

#include <bits/stdc++.h>
using namespace std;

struct Node { Node* next[26] = {}; string word; };

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    Node* root = new Node();
    for (string& w : words) {
        Node* cur = root;
        for (char c : w) {
            if (!cur->next[c - 'a']) cur->next[c - 'a'] = new Node();
            cur = cur->next[c - 'a'];
        }
        cur->word = w;
    }
    int m = board.size(), n = board[0].size();
    vector<string> res;
    function<void(int,int,Node*)> dfs = [&](int r, int c, Node* node) {
        if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] == '#') return;
        char ch = board[r][c];
        Node* nxt = node->next[ch - 'a'];
        if (!nxt) return;
        if (!nxt->word.empty()) { res.push_back(nxt->word); nxt->word.clear(); }
        board[r][c] = '#';
        dfs(r+1,c,nxt); dfs(r-1,c,nxt); dfs(r,c+1,nxt); dfs(r,c-1,nxt);
        board[r][c] = ch;
    };
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            dfs(i, j, root);
    return res;
}