Problem #212: Word Search II

Intuition & Strategy Breakdown

Insert dictionary words into a Trie, then run DFS search from each cell in grid matching Trie nodes while backtracking visited cells.

Python Solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.word = ""

    def add_word(self, word):
        node = self
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
        node.word = word

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            root.add_word(w)
        
        rows, cols = len(board), len(board[0])
        res, visit = set(), set()
        
        def dfs(r, c, node):
            if (r < 0 or c < 0 or 
                r >= rows or c >= cols or
                (r, c) in visit or 
                board[r][c] not in node.children):
                return
            
            visit.add((r, c))
            node = node.children[board[r][c]]
            if node.is_word:
                res.add(node.word)
            
            dfs(r + 1, c, node)
            dfs(r - 1, c, node)
            dfs(r, c + 1, node)
            dfs(r, c - 1, node)
            
            visit.remove((r, c))

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)
        
        return list(res)

Java Solution

class TrieNode {
    HashMap children = new HashMap<>();
    String word = null;
}

class Solution {
    public List findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                if (!node.children.containsKey(c)) {
                    node.children.put(c, new TrieNode());
                }
                node = node.children.get(c);
            }
            node.word = w;
        }

        List res = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root, res);
            }
        }
        return res;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node, List res) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] == '#' || !node.children.containsKey(board[r][c])) {
            return;
        }

        char temp = board[r][c];
        node = node.children.get(temp);
        if (node.word != null) {
            res.add(node.word);
            node.word = null; // Optimization: avoid duplicates and prune
        }

        board[r][c] = '#';
        dfs(board, r + 1, c, node, res);
        dfs(board, r - 1, c, node, res);
        dfs(board, r, c + 1, node, res);
        dfs(board, r, c - 1, node, res);
        board[r][c] = temp;
    }
}