Word Search II LeetCode 212

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

Approach: Trie + DFS Backtracking

Why Trie + DFS?

Approach	Complexity	Issue
Brute Force DFS for each word	O(words × M×N × 4^L)	Too slow
Trie + Single DFS	O(M×N × 4^L)	✓ Optimal

The Trie allows us to prune paths early - if the current prefix doesn't exist in the Trie, we stop exploring that direction immediately.

Board Traversal Example

4-directional movement: From any cell, we can move ↑ ↓ ← →

Complexity

• Time: $O(M \times N \times 4^L)$ where L is max word length (with Trie optimization).
• Space: $O(K \times L)$ for Trie storing K words.

Solution

public IList<string> FindWords(char[][] board, string[] words)
{
    List<string> result = new List<string>();
    List<char> temp = new List<char>();
    Trie t = new Trie();
    bool[,] visited = new bool[board.Length, board[0].Length];
    foreach (var word in words)
    {
        t.Insert(word);
    }
    for (int i = 0; i < board.Length; i++)
    {
        for (int j = 0; j < board[0].Length; j++)
        {
            FindWords(board, words, result, temp, i, j, t, visited);
        }
    }
    return result;

}

public void FindWords(char[][] board, string[] words, List<string> result, List<char> temp, int i, int j, Trie t, bool[,] visited)
{
    int m = board.Length, n = board[0].GetLength(0);
    if (t.Search(temp))
    {
        result.Add(new string(temp.ToArray()));
        return;
    }
    if (i < 0 || j < 0 || i >= m || j >= n || visited[i, j] || !t.StartsWith(temp)) return;

    visited[i, j] = true;
    temp.Add(board[i][j]);
    FindWords(board, words, result, temp, i + 1, j, t, visited);
    FindWords(board, words, result, temp, i - 1, j, t, visited);
    FindWords(board, words, result, temp, i, j + 1, t, visited);
    FindWords(board, words, result, temp, i, j - 1, t, visited);
    temp.RemoveAt(temp.Count - 1);
    visited[i, j] = false;
}

public class Trie
{
    TrieNode root;
    public Trie()
    {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void Insert(string word)
    {
        var current = root;
        foreach (var c in word)
        {
            if (current == null || current.children[c - 'a'] == null)
                current.children[c - 'a'] = new TrieNode();
            current = current.children[c - 'a'];
        }
        current.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public bool Search(List<char> word)
    {
        var current = root;
        foreach (var c in word)
        {
            if (current == null || current.children[c - 'a'] == null)
                return false;
            current = current.children[c - 'a'];
        }
        // added condition for de-duplication
        if (current.isWord)
        {
            current.isWord = false;
            return true;
        }
        return false;
    }
    public bool StartsWith(List<char> word)
    {
        var current = root;
        foreach (var c in word)
        {
            if (current == null || current.children[c - 'a'] == null)
                return false;
            current = current.children[c - 'a'];
        }
        return true;
    }
}

public class TrieNode
{
    public TrieNode[] children;
    public bool isWord;
    public TrieNode()
    {
        children = new TrieNode[26];
    }
};

Key Insights

Interview Tips

• De-duplication trick: Set isWord = false after finding a word to avoid duplicates
• Pruning is key: StartsWith check prunes invalid paths early
• Backtracking pattern: Mark visited → recurse → unmark visited