Word Search II — Trie + Grid DFS Pruning

Problem

Given an m x n board of characters and a list of words, find all words that exist in the board (connected adjacent cells, no reuse).

Approach — Trie + Grid DFS

Insert all words into a trie
DFS from every cell, traversing trie nodes simultaneously
Prune when no trie path exists (key speedup over naive DFS per word)
Mark found words in trie to avoid duplicates; delete word nodes to prune further

Time: O(MN4*3^(L-1)) pruned by trie | Space: O(total word chars)

Solutions

Python

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        root={}
        for word in words:
            node=root
            for c in word:
                if c not in node: node[c]={}
                node=node[c]
            node['#']=word
        R,C=len(board),len(board[0])
        result=[]
        def dfs(node,r,c):
            ch=board[r][c]
            if ch not in node: return
            next_node=node[ch]
            if '#' in next_node:
                result.append(next_node['#'])
                del next_node['#']
            board[r][c]='#'
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                nr,nc=r+dr,c+dc
                if 0<=nr<R and 0<=nc<C: dfs(next_node,nr,nc)
            board[r][c]=ch
            if not next_node: del node[ch]
        for r in range(R):
            for c in range(C): dfs(root,r,c)
        return result

C++

class Solution {
    struct Node{unordered_map<char,Node*>ch;string word;};
    Node* root=new Node();
    int R,C;
    vector<string> res;
    void dfs(vector<vector<char>>& b,Node* n,int r,int c){
        char ch=b[r][c];
        if(ch=='#'||!n->ch.count(ch)) return;
        Node* nx=n->ch[ch];
        if(!nx->word.empty()){res.push_back(nx->word);nx->word="";}
        b[r][c]='#';
        int dr[]={0,0,1,-1},dc[]={1,-1,0,0};
        for(int i=0;i<4;i++){int nr=r+dr[i],nc=c+dc[i];if(nr>=0&&nr<R&&nc>=0&&nc<C)dfs(b,nx,nr,nc);}
        b[r][c]=ch;
    }
public:
    vector<string> findWords(vector<vector<char>>& b,vector<string>& words){
        R=b.size();C=b[0].size();
        for(auto& w:words){Node* c=root;for(char x:w){if(!c->ch[x])c->ch[x]=new Node();c=c->ch[x];}c->word=w;}
        for(int r=0;r<R;r++) for(int c=0;c<C;c++) dfs(b,root,r,c);
        return res;
    }
};

Complexity

Time: O(MN4*3^(L-1)) pruned | Space: O(sum of word lengths)