Word search II

212.Word Search II

Trie

Depth-First Search

Matrix

Backtracking

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. The same letter cell may not be used more than once in a word.

Example:

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"]

Algorithm:

1. Build Trie from word list
2. DFS from each cell in board
3. Use backtracking to mark visited cells
4. Store words in Trie nodes

Complexity:

Time: O(M * N * 4^L) where M, N are board dimensions, L is max word length

Java Solution:

class Solution {
    Trie root;
    
    public List findWords(char[][] board, String[] words) {
        // Initialize result and Trie
        List res = new ArrayList<>();
        root = new Trie();
        
        // Build Trie from words
        for (String word : words) insert(word);
        
        int m = board.length, n = board[0].length;
        
        // Try DFS from each cell
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, root, res, i, j, m, n);
            }
        }
        
        return res;
    }
    
    private void dfs(char[][] board, Trie curr, List res, 
                           int i, int j, int m, int n) {
        // Found a word, add to result and clear to avoid duplicates
        if (curr.word != null) {
            res.add(curr.word);
            curr.word = null;
        }
        
        // Check boundaries and visited cells
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] == '#') 
            return;
        
        char c = board[i][j];
        
        // Check if character exists in Trie
        if (!curr.children.containsKey(c)) return;
        
        // Mark cell as visited
        board[i][j] = '#';
        
        // Recursively check all directions
        Trie next = curr.children.get(c);
        dfs(board, next, res, i + 1, j, m, n);
        dfs(board, next, res, i - 1, j, m, n);
        dfs(board, next, res, i, j + 1, m, n);
        dfs(board, next, res, i, j - 1, m, n);
        
        // Restore cell
        board[i][j] = c;
    }
    
    // Trie node definition
    class Trie {
        String word;
        Map children = new HashMap<>();
    }
    
    // Insert word into Trie
    private void insert(String word) {
        Trie curr = root;
        for (char c : word.toCharArray()) {
            curr.children.putIfAbsent(c, new Trie());
            curr = curr.children.get(c);
        }
        curr.word = word;
    }
}

Python Solution:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Build Trie
        root = TrieNode()
        for word in words:
            curr = root
            for c in word:
                if c not in curr.children:
                    curr.children[c] = TrieNode()
                curr = curr.children[c]
            curr.word = word
            
        rows, cols = len(board), len(board[0])
        result = []
        
        def dfs(i: int, j: int, node: TrieNode):
            # Found word
            if node.word:
                result.append(node.word)
                node.word = None
                
            # Check boundaries and visited
            if (i < 0 or i >= rows or 
                j < 0 or j >= cols or 
                board[i][j] == '#'):
                return
                
            c = board[i][j]
            if c not in node.children:
                return
                
            board[i][j] = '#'  # Mark visited
            
            # Search all directions
            for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
                dfs(i + di, j + dj, node.children[c])
                
            board[i][j] = c  # Restore cell
            
        # Start DFS from each cell
        for i in range(rows):
            for j in range(cols):
                dfs(i, j, root)
                
        return result

C++ Solution:

class Solution {
    struct TrieNode {
        string* word;
        unordered_map<char, TrieNode*> children;
        TrieNode() : word(nullptr) {}
    };
    
    TrieNode* buildTrie(vector& words) {
        TrieNode* root = new TrieNode();
        for (string& word : words) {
            TrieNode* curr = root;
            for (char c : word) {
                if (!curr->children.count(c))
                    curr->children[c] = new TrieNode();
                curr = curr->children[c];
            }
            curr->word = &word;
        }
        return root;
    }
    
    void dfs(vectorchar>>& board, int i, int j,
            TrieNode* node, vector& result) {
        if (node->word != nullptr) {
            result.push_back(*node->word);
            node->word = nullptr;
        }
        
        if (i < 0 || i >= board.size() || j < 0 || 
            j >= board[0].size() || board[i][j] == '#')
            return;
            
        char c = board[i][j];
        if (!node->children.count(c)) return;
        
        board[i][j] = '#';
        
        dfs(board, i+1, j, node->children[c], result);
        dfs(board, i-1, j, node->children[c], result);
        dfs(board, i, j+1, node->children[c], result);
        dfs(board, i, j-1, node->children[c], result);
        
        board[i][j] = c;
    }
    
public:
    vector findWords(vectorchar>>& board, 
                            vector& words) {
        vector result;
        TrieNode* root = buildTrie(words);
        
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++)
                dfs(board, i, j, root, result);
                
        return result;
    }
};