Word Search II (Multiple Words in Grid)

🎯

Word Search II (Multiple Words in Grid)

hardTRIEAmazonFacebookGoogle

Imagine you have a giant crossword puzzle and a huge dictionary of words. You want to find all the words from the dictionary that appear in the puzzle by connecting adjacent letters.

💡 This problem combines searching multiple words in a grid with efficient prefix checking. Beginners often struggle because naive search for each word is too slow, and understanding how to prune searches using a Trie is key.

📋

Problem Statement

Given a 2D board of characters and a list of words, find all words in 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.

1 <= board.length, board[i].length <= 121 <= words.length <= 3 * 10^41 <= words[i].length <= 10board and words consist of lowercase English letters

💡

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

The words 'eat' and 'oath' can be formed by adjacent letters in the board, while 'pea' and 'rain' cannot.

• Empty board → returns empty list
• Empty words list → returns empty list
• Words with repeated letters requiring careful backtracking → correct detection
• Board with all identical letters and multiple words → handles duplicates correctly

⚠️

Common Mistakes

Not marking visited cells properly

Leads to revisiting same cell multiple times causing incorrect words or infinite loops

✅ Use a visited array or mark cells temporarily during DFS

Not pruning DFS when prefix not in Trie

Causes exponential time and TLE on large inputs

✅ Check if current character exists in Trie children before continuing DFS

Adding duplicate words multiple times

Output contains repeated words

✅ Set node.word = None/null after adding to result to avoid duplicates

Modifying board without restoring after DFS

Subsequent DFS calls see corrupted board leading to wrong answers

✅ Restore board cell after DFS call (backtracking)

Not handling empty board or empty words list

Code may crash or return incorrect results

✅ Add checks for empty inputs before processing

🧠

Brute Force (Check Each Word Individually with DFS)

💡 This approach is the most straightforward: for each word, search the entire board to see if it exists. It is slow but helps understand the problem deeply before optimization.

Intuition

Try to find each word by starting a DFS from every cell in the board, checking if the word can be formed by adjacent letters.

Algorithm

1. For each word in the list:
2. For each cell in the board:
3. Start a DFS to check if the word can be formed starting from that cell.
4. If found, add the word to the result list.

💡 The nested loops and DFS make it hard to see the exponential time complexity at first glance.

</>

Code

from typing import List

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0] or not words:
            return []
        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r, c, word, idx, visited):
            if idx == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return False
            if (r, c) in visited or board[r][c] != word[idx]:
                return False
            visited.add((r, c))
            res = (dfs(r+1, c, word, idx+1, visited) or dfs(r-1, c, word, idx+1, visited) or
                   dfs(r, c+1, word, idx+1, visited) or dfs(r, c-1, word, idx+1, visited))
            visited.remove((r, c))
            return res

        for word in words:
            found = False
            for r in range(rows):
                for c in range(cols):
                    if dfs(r, c, word, 0, set()):
                        result.append(word)
                        found = True
                        break
                if found:
                    break
        return result

# Driver code
if __name__ == '__main__':
    board = [
        ['o','a','a','n'],
        ['e','t','a','e'],
        ['i','h','k','r'],
        ['i','f','l','v']
    ]
    words = ["oath","pea","eat","rain"]
    sol = Solution()
    print(sol.findWords(board, words))

Line Notes

def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:Main function to find all words by checking each word individually

if not board or not board[0] or not words:Handle empty board or empty words list edge cases

def dfs(r, c, word, idx, visited):DFS helper to check if a single word exists starting at (r,c)

if idx == len(word):Base case: all characters matched successfully

if (r, c) in visited or board[r][c] != word[idx]:Avoid revisiting cells and check character match

visited.add((r, c))Mark current cell as visited before exploring neighbors

visited.remove((r, c))Backtrack: unmark cell after exploring

for word in words:Iterate over all words to check individually

if dfs(r, c, word, 0, set()):If word found starting at this cell, add to result

return resultReturn all found words after checking all

import java.util.*;

public class Solution {
    private int rows, cols;
    private char[][] board;
    private boolean[][] visited;
    private String word;

    public boolean dfs(int r, int c, int idx) {
        if (idx == word.length()) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
        if (visited[r][c] || board[r][c] != word.charAt(idx)) return false;
        visited[r][c] = true;
        boolean res = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1) || dfs(r, c+1, idx+1) || dfs(r, c-1, idx+1);
        visited[r][c] = false;
        return res;
    }

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        rows = board.length;
        cols = board[0].length;
        List<String> result = new ArrayList<>();
        for (String w : words) {
            this.word = w;
            visited = new boolean[rows][cols];
            boolean found = false;
            for (int r = 0; r < rows && !found; r++) {
                for (int c = 0; c < cols && !found; c++) {
                    if (dfs(r, c, 0)) {
                        result.add(w);
                        found = true;
                    }
                }
            }
        }
        return result;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] board = {
            {'o','a','a','n'},
            {'e','t','a','e'},
            {'i','h','k','r'},
            {'i','f','l','v'}
        };
        String[] words = {"oath","pea","eat","rain"};
        System.out.println(sol.findWords(board, words));
    }
}

Line Notes

public boolean dfs(int r, int c, int idx)DFS helper to check if word exists starting at (r,c)

if (idx == word.length()) return true;All characters matched base case

visited[r][c] = true;Mark cell visited before recursion

visited[r][c] = false;Backtrack after recursion

for (String w : words)Iterate over each word to check

boolean found = false;Flag to stop searching once word found

if (dfs(r, c, 0))Start DFS from each cell

return result;Return list of found words

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
    int rows, cols;
    vector<vector<char>> board;
    vector<vector<bool>> visited;
    string word;

    bool dfs(int r, int c, int idx) {
        if (idx == word.size()) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
        if (visited[r][c] || board[r][c] != word[idx]) return false;
        visited[r][c] = true;
        bool res = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1) || dfs(r, c+1, idx+1) || dfs(r, c-1, idx+1);
        visited[r][c] = false;
        return res;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        this->board = board;
        rows = board.size();
        cols = board[0].size();
        vector<string> result;
        for (auto& w : words) {
            word = w;
            visited.assign(rows, vector<bool>(cols, false));
            bool found = false;
            for (int r = 0; r < rows && !found; r++) {
                for (int c = 0; c < cols && !found; c++) {
                    if (dfs(r, c, 0)) {
                        result.push_back(w);
                        found = true;
                    }
                }
            }
        }
        return result;
    }
};

// Driver code
int main() {
    vector<vector<char>> board = {
        {'o','a','a','n'},
        {'e','t','a','e'},
        {'i','h','k','r'},
        {'i','f','l','v'}
    };
    vector<string> words = {"oath","pea","eat","rain"};
    Solution sol;
    vector<string> res = sol.findWords(board, words);
    for (auto& w : res) cout << w << " ";
    cout << endl;
    return 0;
}

Line Notes

bool dfs(int r, int c, int idx)DFS function to check word existence from position

if (idx == word.size()) return true;Base case: all letters matched

visited[r][c] = true;Mark cell visited before exploring neighbors

visited[r][c] = false;Backtrack to allow other paths

for (auto& w : words)Check each word individually

bool found = false;Stop searching once word found

if (dfs(r, c, 0))Start DFS from each cell

return result;Return all found words

var findWords = function(board, words) {
    const rows = board.length, cols = board[0].length;
    const result = [];

    function dfs(r, c, word, idx, visited) {
        if (idx === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
        if (visited.has(r + ',' + c) || board[r][c] !== word[idx]) return false;
        visited.add(r + ',' + c);
        const res = dfs(r+1, c, word, idx+1, visited) || dfs(r-1, c, word, idx+1, visited) || dfs(r, c+1, word, idx+1, visited) || dfs(r, c-1, word, idx+1, visited);
        visited.delete(r + ',' + c);
        return res;
    }

    for (const word of words) {
        let found = false;
        for (let r = 0; r < rows && !found; r++) {
            for (let c = 0; c < cols && !found; c++) {
                if (dfs(r, c, word, 0, new Set())) {
                    result.push(word);
                    found = true;
                }
            }
        }
    }
    return result;
};

// Driver code
const board = [
    ['o','a','a','n'],
    ['e','t','a','e'],
    ['i','h','k','r'],
    ['i','f','l','v']
];
const words = ["oath","pea","eat","rain"];
console.log(findWords(board, words));

Line Notes

function dfs(r, c, word, idx, visited)DFS helper to check if word exists starting at (r,c)

if (idx === word.length) return true;All characters matched base case

visited.add(r + ',' + c);Mark cell visited before recursion

visited.delete(r + ',' + c);Backtrack after recursion

for (const word of words)Iterate over each word to check

if (dfs(r, c, word, 0, new Set()))Start DFS from each cell

return result;Return all found words

⏱

Complexity

TimeO(W * N * 4^L) where W = number of words, N = number of cells, L = max word length

SpaceO(L) recursion stack + O(N) visited set

For each word, we start DFS from each cell. Each DFS explores up to 4 directions for each character, leading to exponential time in word length.

💡 For a 12x12 board (144 cells) and word length 10, this approach tries up to 4^10 paths per word, which is huge and impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem and motivate optimization.

🧠

Trie + DFS (Prefix Pruning)

💡 Using a Trie to store all words allows pruning DFS paths early if no word starts with the current prefix, drastically reducing search space.

Intuition

Build a Trie of all words, then DFS on the board checking prefixes in the Trie. If prefix not found, stop exploring that path.

Algorithm

1. Build a Trie from the list of words.
2. For each cell in the board, start DFS with the Trie root.
3. At each step, check if current prefix exists in Trie; if not, backtrack.
4. If a word ends at current Trie node, add it to results and mark as found to avoid duplicates.

💡 The key is combining Trie prefix checks with DFS to prune impossible paths early.

</>

Code

from typing import List

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

class Solution:
    def buildTrie(self, words):
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word = w
        return root

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = self.buildTrie(words)
        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r, c, node):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            char = board[r][c]
            if char == '#' or char not in node.children:
                return
            node = node.children[char]
            if node.word:
                result.append(node.word)
                node.word = None  # avoid duplicates
            board[r][c] = '#'
            dfs(r+1, c, node)
            dfs(r-1, c, node)
            dfs(r, c+1, node)
            dfs(r, c-1, node)
            board[r][c] = char

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

# Driver code
if __name__ == '__main__':
    board = [
        ['o','a','a','n'],
        ['e','t','a','e'],
        ['i','h','k','r'],
        ['i','f','l','v']
    ]
    words = ["oath","pea","eat","rain"]
    sol = Solution()
    print(sol.findWords(board, words))

Line Notes

class TrieNode:Define Trie node with children and word field

def buildTrie(self, words):Build Trie from all words for prefix checks

if node.word:Found a complete word, add to result and mark None to avoid duplicates

board[r][c] = '#'Mark cell visited in-place to save space

board[r][c] = charRestore cell after DFS backtracking

if char == '#' or char not in node.children:Prune DFS if no prefix matches

for r in range(rows):Start DFS from every cell

return resultReturn all found words

import java.util.*;

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

public class Solution {
    private int rows, cols;
    private char[][] board;
    private List<String> result = new ArrayList<>();

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.word = w;
        }
        return root;
    }

    private void dfs(int r, int c, TrieNode node) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        char ch = board[r][c];
        if (ch == '#' || !node.children.containsKey(ch)) return;
        node = node.children.get(ch);
        if (node.word != null) {
            result.add(node.word);
            node.word = null; // avoid duplicates
        }
        board[r][c] = '#';
        dfs(r+1, c, node);
        dfs(r-1, c, node);
        dfs(r, c+1, node);
        dfs(r, c-1, node);
        board[r][c] = ch;
    }

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        rows = board.length;
        cols = board[0].length;
        TrieNode root = buildTrie(words);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dfs(r, c, root);
            }
        }
        return result;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] board = {
            {'o','a','a','n'},
            {'e','t','a','e'},
            {'i','h','k','r'},
            {'i','f','l','v'}
        };
        String[] words = {"oath","pea","eat","rain"};
        System.out.println(sol.findWords(board, words));
    }
}

Line Notes

class TrieNode {Trie node with children map and word field

TrieNode buildTrie(String[] words)Build Trie for prefix pruning

if (node.word != null)Found a word, add to result and mark null to avoid duplicates

board[r][c] = '#'Mark cell visited in-place

board[r][c] = ch;Restore cell after DFS

if (ch == '#' || !node.children.containsKey(ch)) return;Prune DFS if prefix not found

for (int r = 0; r < rows; r++)Start DFS from every cell

return result;Return all found words

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    string word = "";
};

class Solution {
    int rows, cols;
    vector<vector<char>> board;
    vector<string> result;

    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (auto& w : words) {
            TrieNode* node = root;
            for (char c : w) {
                if (!node->children.count(c))
                    node->children[c] = new TrieNode();
                node = node->children[c];
            }
            node->word = w;
        }
        return root;
    }

    void dfs(int r, int c, TrieNode* node) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        char ch = board[r][c];
        if (ch == '#' || node->children.find(ch) == node->children.end()) return;
        node = node->children[ch];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word = ""; // avoid duplicates
        }
        board[r][c] = '#';
        dfs(r+1, c, node);
        dfs(r-1, c, node);
        dfs(r, c+1, node);
        dfs(r, c-1, node);
        board[r][c] = ch;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        this->board = board;
        rows = board.size();
        cols = board[0].size();
        TrieNode* root = buildTrie(words);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dfs(r, c, root);
            }
        }
        return result;
    }
};

// Driver code
int main() {
    vector<vector<char>> board = {
        {'o','a','a','n'},
        {'e','t','a','e'},
        {'i','h','k','r'},
        {'i','f','l','v'}
    };
    vector<string> words = {"oath","pea","eat","rain"};
    Solution sol;
    vector<string> res = sol.findWords(board, words);
    for (auto& w : res) cout << w << " ";
    cout << endl;
    return 0;
}

Line Notes

struct TrieNode {Trie node with children map and word string

TrieNode* buildTrie(vector<string>& words)Build Trie for prefix pruning

if (!node->word.empty())Found a word, add to result and clear to avoid duplicates

board[r][c] = '#'Mark cell visited in-place

board[r][c] = ch;Restore cell after DFS

if (ch == '#' || node->children.find(ch) == node->children.end()) return;Prune DFS if prefix not found

for (int r = 0; r < rows; r++)Start DFS from every cell

return result;Return all found words

var findWords = function(board, words) {
    const rows = board.length, cols = board[0].length;
    const result = [];

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

    const buildTrie = (words) => {
        const root = new TrieNode();
        for (const w of words) {
            let node = root;
            for (const c of w) {
                if (!node.children.has(c)) node.children.set(c, new TrieNode());
                node = node.children.get(c);
            }
            node.word = w;
        }
        return root;
    };

    const root = buildTrie(words);

    const dfs = (r, c, node) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        const ch = board[r][c];
        if (ch === '#' || !node.children.has(ch)) return;
        node = node.children.get(ch);
        if (node.word !== null) {
            result.push(node.word);
            node.word = null; // avoid duplicates
        }
        board[r][c] = '#';
        dfs(r+1, c, node);
        dfs(r-1, c, node);
        dfs(r, c+1, node);
        dfs(r, c-1, node);
        board[r][c] = ch;
    };

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

// Driver code
const board = [
    ['o','a','a','n'],
    ['e','t','a','e'],
    ['i','h','k','r'],
    ['i','f','l','v']
];
const words = ["oath","pea","eat","rain"];
console.log(findWords(board, words));

Line Notes

class TrieNode {Trie node with children map and word field

const buildTrie = (words) => {Build Trie for prefix pruning

if (node.word !== null)Found a word, add to result and mark null to avoid duplicates

board[r][c] = '#';Mark cell visited in-place

board[r][c] = ch;Restore cell after DFS

if (ch === '#' || !node.children.has(ch)) return;Prune DFS if prefix not found

for (let r = 0; r < rows; r++)Start DFS from every cell

return result;Return all found words

⏱

Complexity

TimeO(M * 4 * 3^L) where M = number of cells, L = max word length

SpaceO(N) for Trie + O(L) recursion stack

Trie pruning reduces unnecessary DFS paths drastically compared to brute force. Each DFS explores only valid prefixes.

💡 For a 12x12 board and word length 10, pruning cuts down the search space from 4^10 to roughly 3^10 per start cell.

Interview Verdict: Accepted

This approach is efficient enough for large inputs and is the standard solution in interviews.

🧠

Trie + DFS with In-place Trie Node Pruning

💡 Further optimize by removing leaf Trie nodes after finding words to reduce search space dynamically during DFS.

Intuition

After finding a word, delete its leaf node in the Trie to prevent redundant searches and speed up subsequent DFS calls.

Algorithm

1. Build Trie from words.
2. DFS on board with Trie root.
3. When a word is found, add to result and remove word from Trie node.
4. If a Trie node has no children after removal, delete it from its parent to prune the Trie.
5. Continue DFS with pruned Trie to reduce search space.

💡 This dynamic pruning reduces the Trie size during search, improving efficiency especially with many overlapping prefixes.

</>

Code

from typing import List

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

class Solution:
    def buildTrie(self, words):
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word = w
        return root

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = self.buildTrie(words)
        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r, c, node):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            char = board[r][c]
            if char == '#' or char not in node.children:
                return
            node = node.children[char]
            if node.word:
                result.append(node.word)
                node.word = None  # avoid duplicates
            board[r][c] = '#'
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                dfs(r+dr, c+dc, node)
            board[r][c] = char

            # Note: Proper pruning requires parent reference, omitted here for simplicity

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

# Driver code
if __name__ == '__main__':
    board = [
        ['o','a','a','n'],
        ['e','t','a','e'],
        ['i','h','k','r'],
        ['i','f','l','v']
    ]
    words = ["oath","pea","eat","rain"]
    sol = Solution()
    print(sol.findWords(board, words))

Line Notes

if node.word:Add found word and mark None to avoid duplicates

board[r][c] = '#'Mark cell visited in-place

board[r][c] = charRestore cell after DFS

for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:Explore all 4 directions

# Note: Proper pruning requires parent reference, omitted here for simplicityPruning leaf nodes requires parent pointer; omitted to avoid incorrect code

import java.util.*;

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

public class Solution {
    private int rows, cols;
    private char[][] board;
    private List<String> result = new ArrayList<>();

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.word = w;
        }
        return root;
    }

    private void dfs(int r, int c, TrieNode node) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        char ch = board[r][c];
        if (ch == '#' || !node.children.containsKey(ch)) return;
        node = node.children.get(ch);
        if (node.word != null) {
            result.add(node.word);
            node.word = null; // avoid duplicates
        }
        board[r][c] = '#';
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};
        for (int i = 0; i < 4; i++) {
            dfs(r + dr[i], c + dc[i], node);
        }
        board[r][c] = ch;

        // Note: Proper pruning requires parent reference, omitted here
    }

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        rows = board.length;
        cols = board[0].length;
        TrieNode root = buildTrie(words);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dfs(r, c, root);
            }
        }
        return result;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] board = {
            {'o','a','a','n'},
            {'e','t','a','e'},
            {'i','h','k','r'},
            {'i','f','l','v'}
        };
        String[] words = {"oath","pea","eat","rain"};
        System.out.println(sol.findWords(board, words));
    }
}

Line Notes

if (node.word != null)Add found word and mark null to avoid duplicates

board[r][c] = '#'Mark cell visited in-place

board[r][c] = ch;Restore cell after DFS

for (int i = 0; i < 4; i++)Explore all 4 directions

// Note: Proper pruning requires parent reference, omitted herePruning leaf nodes requires parent pointer; omitted to avoid incorrect code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    string word = "";
};

class Solution {
    int rows, cols;
    vector<vector<char>> board;
    vector<string> result;

    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (auto& w : words) {
            TrieNode* node = root;
            for (char c : w) {
                if (!node->children.count(c))
                    node->children[c] = new TrieNode();
                node = node->children[c];
            }
            node->word = w;
        }
        return root;
    }

    void dfs(int r, int c, TrieNode* node) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        char ch = board[r][c];
        if (ch == '#' || node->children.find(ch) == node->children.end()) return;
        node = node->children[ch];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word = ""; // avoid duplicates
        }
        board[r][c] = '#';
        dfs(r+1, c, node);
        dfs(r-1, c, node);
        dfs(r, c+1, node);
        dfs(r, c-1, node);
        board[r][c] = ch;

        // Note: Proper pruning requires parent reference, omitted here
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        this->board = board;
        rows = board.size();
        cols = board[0].size();
        TrieNode* root = buildTrie(words);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dfs(r, c, root);
            }
        }
        return result;
    }
};

// Driver code
int main() {
    vector<vector<char>> board = {
        {'o','a','a','n'},
        {'e','t','a','e'},
        {'i','h','k','r'},
        {'i','f','l','v'}
    };
    vector<string> words = {"oath","pea","eat","rain"};
    Solution sol;
    vector<string> res = sol.findWords(board, words);
    for (auto& w : res) cout << w << " ";
    cout << endl;
    return 0;
}

Line Notes

if (!node->word.empty())Add found word and clear to avoid duplicates

board[r][c] = '#'Mark cell visited in-place

board[r][c] = ch;Restore cell after DFS

dfs(r+1, c, node);Explore down

dfs(r-1, c, node);Explore up

dfs(r, c+1, node);Explore right

dfs(r, c-1, node);Explore left

// Note: Proper pruning requires parent reference, omitted herePruning leaf nodes requires parent pointer; omitted to avoid incorrect code

var findWords = function(board, words) {
    const rows = board.length, cols = board[0].length;
    const result = [];

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

    const buildTrie = (words) => {
        const root = new TrieNode();
        for (const w of words) {
            let node = root;
            for (const c of w) {
                if (!node.children.has(c)) node.children.set(c, new TrieNode());
                node = node.children.get(c);
            }
            node.word = w;
        }
        return root;
    };

    const root = buildTrie(words);

    const dfs = (r, c, node) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        const ch = board[r][c];
        if (ch === '#' || !node.children.has(ch)) return;
        node = node.children.get(ch);
        if (node.word !== null) {
            result.push(node.word);
            node.word = null; // avoid duplicates
        }
        board[r][c] = '#';
        [[1,0],[-1,0],[0,1],[0,-1]].forEach(([dr, dc]) => dfs(r+dr, c+dc, node));
        board[r][c] = ch;

        // Note: Proper pruning requires parent reference, omitted here
    };

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

// Driver code
const board = [
    ['o','a','a','n'],
    ['e','t','a','e'],
    ['i','h','k','r'],
    ['i','f','l','v']
];
const words = ["oath","pea","eat","rain"];
console.log(findWords(board, words));

Line Notes

if (node.word !== null)Add found word and mark null to avoid duplicates

board[r][c] = '#';Mark cell visited in-place

board[r][c] = ch;Restore cell after DFS

[[1,0],[-1,0],[0,1],[0,-1]].forEach(([dr, dc]) => dfs(r+dr, c+dc, node));Explore all 4 directions

// Note: Proper pruning requires parent reference, omitted herePruning leaf nodes requires parent pointer; omitted to avoid incorrect code

⏱

Complexity

TimeSimilar to approach 2 but with better pruning in practice

SpaceO(N) Trie + O(L) recursion stack

Pruning Trie nodes reduces the search space dynamically, improving runtime especially with many overlapping prefixes.

💡 This optimization is subtle but can make a big difference in large inputs with many words sharing prefixes.

Interview Verdict: Accepted

This is the most optimized standard solution and often expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (Trie + DFS) is the best balance of clarity and efficiency for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(W * N * 4^L)	O(L) recursion stack + O(N) visited	Yes (deep recursion for long words)	Yes	Mention only - never code due to inefficiency
2. Trie + DFS	O(M * 4 * 3^L)	O(N) Trie + O(L) recursion stack	Less risk due to pruning	Yes	Code this approach in interviews
3. Trie + DFS with Trie Pruning	Better than approach 2 in practice	O(N) Trie + O(L) recursion stack	Less risk	Yes	Mention as optimization if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Describe brute force approach and its limitations.Step 3: Introduce Trie data structure and prefix pruning.Step 4: Explain Trie + DFS approach with pruning.Step 5: Discuss further Trie pruning optimization if asked.Step 6: Code the Trie + DFS solution carefully.Step 7: Test with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Explain: 7min. Total ~30min

What the Interviewer Tests

Ability to combine data structures (Trie) with backtracking, optimize search with pruning, and write clean, bug-free code.

Common Follow-ups

• What if board is very large but words are few? → Use Trie but limit DFS starts.
• How to handle duplicate words in input? → Use Trie word field and mark found words null.
• Can we use iterative DFS? → Possible but recursion is cleaner here.
• What if diagonal moves are allowed? → Add diagonal directions in DFS.

💡 These follow-ups test understanding of problem variations and robustness of your solution.

🔍

Pattern Recognition

When to Use

1) Multiple words to search, 2) Grid or matrix input, 3) Need to check prefixes efficiently, 4) Backtracking or DFS involved

Signature Phrases

find all wordsadjacent cellsprefix pruningbacktracking

NOT This Pattern When

Single word search without multiple words or prefix pruning is simpler backtracking, not Trie pattern.

Similar Problems

Word Search I - single word search in grid, simpler versionBoggle Game - similar grid word search with dictionary lookup

Practice

1. You are given an array of integers and multiple queries. Each query provides a number x and a limit m. For each query, you must find the maximum XOR of x with any array element less than or equal to m. Which approach guarantees an optimal solution for large inputs?

easy

A. Sort the array and queries, then use a bitwise trie to insert elements up to the query limit and find max XOR.

B. Use dynamic programming to store XOR results for all subarrays and answer queries in O(1).

C. Use a brute force nested loop checking all elements for each query.

D. Apply a greedy approach by always choosing the element with the highest value less than or equal to m.

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; DP for subarrays doesn't apply since queries are arbitrary.

2. Step 2: Recognize the pattern

   Sorting nums and queries allows incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + trie insertion matches known optimal approach [OK]

Hint: Sort queries and nums, then use bit trie [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Using DP for unrelated subproblems
• Greedy max element doesn't guarantee max XOR

2. Consider the following code snippet implementing the optimal trie-based solution for shortest unique prefixes. Given the input words = ["dog", "dove", "duck"], what is the output of shortest_unique_prefix(words)?

easy

A. ["do", "dov", "du"]

B. ["d", "dov", "du"]

C. ["dog", "dove", "duck"]

D. ["dog", "dov", "du"]

Solution

1. Step 1: Trace insertion frequencies

   Insert "dog": d(1), o(1), g(1); "dove": d(2), o(2), v(1), e(1); "duck": d(3), u(1), c(1), k(1).

2. Step 2: Find unique prefixes

   For "dog": prefix "dog" (g freq=1) unique; for "dove": prefix "dov" (v freq=1) unique; for "duck": prefix "du" (u freq=1) unique.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefixes match first node with freq=1 [OK]

Hint: Unique prefix ends where node freq equals 1 [OK]

Common Mistakes:

• Stopping prefix too early
• Assuming first letter always unique

3. Consider the following Python code implementing the optimal StreamChecker. Given the words ["cd", "f", "kl"], what is the return value of the query sequence: query('a'), query('b'), query('c'), query('d')? Specifically, what does query('d') return?

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

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

sc = StreamChecker(["cd", "f", "kl"])
print(sc.query('a'))
print(sc.query('b'))
print(sc.query('c'))
print(sc.query('d'))

easy

A. False

B. True

C. Raises an exception

D. None

Solution

1. Step 1: Trace the stream buffer after queries

   After queries 'a', 'b', 'c', 'd', the stream buffer contains ['a','b','c','d'], but max_len=2, so oldest letters are popped. After 'c', stream=['b','c'], after 'd', stream=['c','d'].

2. Step 2: Traverse trie with reversed stream

   For query('d'), reversed stream is ['d','c']. Trie has reversed words: 'dc' for 'cd'. Traversing 'd' then 'c' hits is_word=True at 'c' node, so returns True. However, the query sequence is query('a'), query('b'), query('c'), query('d'). The query('c') returns False because 'c' alone is not a word. The query('d') returns True because 'cd' is in the dictionary and the stream buffer contains ['c','d'].

3. Step 3: Check query('d') return value

   Since the query('d') returns True, the correct answer is True.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stream buffer limited to max word length matches 'cd' suffix [OK]

Hint: Stream buffer limited to max word length [OK]

Common Mistakes:

• Not limiting stream buffer size
• Not reversing words in trie
• Returning false too early

4. Suppose the problem is modified so that each query asks for the maximum XOR with any array element less than or equal to m, but now elements can be reused multiple times per query. Which modification to the algorithm is correct?

hard

A. Use the same offline trie approach; reuse does not affect XOR calculation.

B. Reuse does not change the problem; just run brute force for each query.

C. Switch to a dynamic programming approach since reuse implies unlimited usage.

D. Modify the trie to store counts of elements and allow multiple traversals per query bit path.

Solution

1. Step 1: Understand reuse impact

   Reusing elements means multiple paths in trie may be valid; counts needed to track availability.

2. Step 2: Modify trie structure

   Store counts at nodes to allow multiple traversals and correct max XOR calculation with reuse.

3. Step 3: Reject naive approaches

   Offline trie without counts ignores reuse; DP or brute force inefficient or incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Counting elements in trie supports reuse [OK]

Hint: Track counts in trie nodes for reuse [OK]

Common Mistakes:

• Ignoring reuse effect on trie
• Assuming reuse is free without data structure changes
• Switching to DP unnecessarily

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the algorithm is necessary to correctly handle this variant?

hard

A. Modify the inner loop to continue checking all prefixes even after dp[i] is set to True

B. Change dp array to count number of ways instead of boolean flags

C. Remove the dp array and use pure recursion with memoization only

D. No change needed; the original DP with trie approach already supports reuse

Solution

1. Step 1: Understand reuse impact on DP

   When reuse is allowed, multiple segmentations can overlap. The DP must consider all possible prefixes, not stop at first True.

2. Step 2: Modify inner loop behavior

   Breaking early when dp[i] is True prevents exploring all segmentations. Removing the break allows full exploration, correctly handling reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing all prefixes ensures reuse is handled [OK]

Hint: Breaking early blocks multiple reuse paths [OK]

Common Mistakes:

• Assuming original DP supports reuse without change
• Changing dp to count ways unnecessarily
• Removing dp and relying on recursion only