Code Implementation

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

class Solution:
    def findWords(self, board, words):
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        rows, cols = len(board), len(board[0])
        res = []

        def dfs(r, c, node):
            char = board[r][c]
            if char not in node.children:
                return
            next_node = node.children[char]
            if next_node.word:
                res.append(next_node.word)
                next_node.word = None  # Avoid duplicates

            board[r][c] = "#"
            for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                    dfs(nr, nc, next_node)
            board[r][c] = char

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

class TrieNode {
public:
    TrieNode* children[26] = {};
    string word = "";
};

class Solution {
public:
    void insert(TrieNode* root, const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->word = word;
    }

    void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node, vector<string>& res) {
        char ch = board[r][c];
        if (ch == '#' || !node->children[ch - 'a']) return;
        node = node->children[ch - 'a'];
        if (node->word != "") {
            res.push_back(node->word);
            node->word = "";
        }
        board[r][c] = '#';
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < board.size() && nc >= 0 && nc < board[0].size())
                dfs(board, nr, nc, node, res);
        }
        board[r][c] = ch;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (auto& word : words) insert(root, word);
        vector<string> res;
        for (int r = 0; r < board.size(); ++r)
            for (int c = 0; c < board[0].size(); ++c)
                dfs(board, r, c, root, res);
        return res;
    }
};
      

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null;
}

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) node.children[idx] = new TrieNode();
                node = node.children[idx];
            }
            node.word = word;
        }
        List<String> res = new ArrayList<>();
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                dfs(board, r, c, root, res);
        return res;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> res) {
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'a'] == null) return;
        node = node.children[ch - 'a'];
        if (node.word != null) {
            res.add(node.word);
            node.word = null;
        }
        board[r][c] = '#';
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length)
                dfs(board, nr, nc, node, res);
        }
        board[r][c] = ch;
    }
}
      

class TrieNode {
    constructor() {
        this.children = {};
        this.word = null;
    }
}

var findWords = function(board, words) {
    const root = new TrieNode();
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children[char]) node.children[char] = new TrieNode();
            node = node.children[char];
        }
        node.word = word;
    }

    const res = [];
    const rows = board.length, cols = board[0].length;

    function dfs(r, c, node) {
        const char = board[r][c];
        if (!node.children[char]) return;
        const nextNode = node.children[char];
        if (nextNode.word) {
            res.push(nextNode.word);
            nextNode.word = null;
        }
        board[r][c] = '#';
        for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
                dfs(nr, nc, nextNode);
            }
        }
        board[r][c] = char;
    }

    for (let r = 0; r < rows; ++r)
        for (let c = 0; c < cols; ++c)
            dfs(r, c, root);

    return res;
};
      

Problem Description

Given a 2D board of characters called board and a list of strings called words, find all words from words that can be formed by sequentially adjacent letters on the board. Each letter cell may only be used once per word.

• Adjacent cells are those horizontally or vertically neighboring.
• You must not use the same cell more than once in a single word.
• Return all words that can be found on the board, with no duplicates.

For example, if board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] and words = ["oath","pea","eat","rain"], the output should be ["eat","oath"].

Thought Process

At first glance, this problem seems similar to a word search puzzle. For each word, you could try to find a path on the board that spells it out, moving up, down, left, or right, and not revisiting any cell for the same word.

The naive approach would be to search for each word independently, starting from every cell and using depth-first search (DFS) to try to spell out the word. However, this quickly becomes inefficient if the board or the word list is large, as we might repeat a lot of the same searches.

To optimize, we notice that many words may share common prefixes. For example, “eat” and “ear” both start with “ea”. Instead of searching for each word separately, we can search for all words simultaneously by building a Trie (prefix tree) from the word list. This way, we only need to explore each path on the board once, and we can check for any word that starts with the current prefix.

The key insight is to combine DFS traversal of the board with prefix matching using the Trie. This avoids repeated work and efficiently finds all matches.

Solution Approach

• Step 1: Build a Trie
  • Insert every word from the words list into a Trie data structure. Each node in the Trie represents a letter, and a complete word is marked at the last letter node.
• Step 2: Start DFS from Each Cell
  • For every cell in the board, start a DFS traversal. At each step, check if the current letter exists as a child in the Trie node.
• Step 3: Traverse and Mark Visited Cells
  • To avoid revisiting the same cell in a path, temporarily mark the cell as visited (e.g., with a special character like '#').
• Step 4: Collect Words
  • If you reach a Trie node that marks the end of a word, add that word to the result list and mark it as found (to avoid duplicates).
• Step 5: Backtrack
  • After exploring all possible directions from a cell, restore its original value so it can be used in other searches.
• Step 6: Return Results
  • After all DFS traversals, return the list of found words.

We use a Trie for fast prefix lookups (O(1) per character), and DFS to explore the board efficiently. This avoids redundant searches and ensures we only find valid words.

Example Walkthrough

Let's use the example:

• board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
• words = ["oath","pea","eat","rain"]

Step 1: Build a Trie with the four words.

Step 2: Start DFS from each cell. Let's say we start at cell (0,0) which is 'o'. We look for words starting with 'o' in the Trie.

Step 3: From (0,0), we can move to (1,0) which is 'e', but 'oe' is not a prefix in the Trie, so we backtrack. Instead, from (0,0), we move to (0,1) which is 'a', forming 'oa', which is a prefix for "oath".

Step 4: Continue DFS, visiting neighboring cells and matching the Trie. Eventually, we spell out "oath" by visiting the path (0,0) → (0,1) → (1,1) → (2,1).

Step 5: Mark "oath" as found, and continue DFS from other starting cells.

Step 6: Similarly, we find "eat" by starting from (1,0) → (1,1) → (1,2).

Step 7: "pea" and "rain" are not found on the board.

The final result is ["oath","eat"].

Time and Space Complexity

• Brute-force Approach:
  • For each word, start DFS from every cell. For a board of size M x N and W words of length L, this is O(W * M * N * 4^L) in the worst case, as each DFS can branch up to 4 directions per letter.
• Optimized Trie + DFS Approach:
  • Building the Trie takes O(T) time, where T is the sum of all word lengths.
  • DFS traversal visits each cell, and in the worst case, explores all possible prefixes, but pruning with the Trie avoids unnecessary paths. The practical time is much less than brute force, but the theoretical worst case is O(M * N * 4^L), where L is the maximum word length.
  • Space complexity is O(T) for the Trie, plus O(L) for the recursion stack and O(T) for the result set.

The use of the Trie significantly reduces redundant searches, making the algorithm efficient for large boards and word lists.

Summary

By combining a Trie for fast prefix checking with DFS for board traversal, we efficiently solve the Word Search II problem. This approach avoids redundant searches by sharing common prefixes and only explores valid paths, making it both elegant and performant. The key insight is to treat the search as a simultaneous exploration for all words, leveraging the Trie to prune dead ends early and collect results as soon as they are found.