Word Search II (Trie + Backtrack)

🎯

Word Search II (Trie + Backtrack)

hardBACKTRACKINGAmazonFacebookGoogle

Imagine you have a large grid of letters and a dictionary of words. You want to find all the words from the dictionary that can be formed by tracing adjacent letters in the grid, like a word puzzle solver.

💡 This problem combines searching a grid with checking multiple words efficiently. Beginners often struggle because naive search for each word is too slow, and managing backtracking with pruning requires careful thought.

📋

Problem Statement

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

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 on the board, 'pea' and 'rain' cannot.

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

⚠️

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 in-place marking and restore after backtracking

Not pruning Trie nodes after word found

Causes redundant searches and slower runtime

✅ Remove Trie nodes with no children after word found to prune search space

Checking each word independently without Trie

Leads to TLE on large inputs

✅ Build a Trie for all words and backtrack once to find all matches

Not handling duplicate words in output

Same word appears multiple times in result

✅ Mark found words as null in Trie to avoid duplicates

Not restoring board state after backtracking

Subsequent searches fail or produce wrong results

✅ Restore original letter after recursive calls

🧠

Brute Force (Search Each Word Individually)

💡 This approach is the most straightforward: for each word, search the board using backtracking. It is slow but helps understand the problem's core mechanics.

Intuition

Try to find each word on the board by starting from every cell and exploring all paths recursively.

Algorithm

1. For each word in the list:
2. For each cell in the board:
3. Use 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 recursive DFS are easy to get lost in; focusing on one word at a time clarifies the process.

</>

Code

from typing import List

def exist(board: List[List[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    visited = [[False]*cols for _ in range(rows)]

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

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    result = []
    for word in words:
        if exist(board, word):
            result.append(word)
    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']
    print(findWords(board, words))

Line Notes

def exist(board: List[List[str]], word: str) -> bool:Defines a helper function to check if a single word exists on the board

visited = [[False]*cols for _ in range(rows)]Tracks visited cells to avoid reusing letters in the same word path

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

visited[r][c] = TrueMark current cell as visited before exploring neighbors

visited[r][c] = FalseBacktrack by unmarking the cell after exploring

for r in range(rows):Try starting DFS from every cell in the board

if dfs(r, c, 0):If DFS finds the word starting at this cell, return True

for word in words:Check each word independently, leading to high time complexity

import java.util.*;

public class WordSearchBrute {
    private static boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;

        // For each cell, try DFS with fresh visited array
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                boolean[][] visited = new boolean[rows][cols];
                if (dfs(board, word, r, c, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

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

    public static List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (exist(board, word)) {
                result.add(word);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        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(findWords(board, words));
    }
}

Line Notes

private static boolean exist(char[][] board, String word)Checks if a single word exists on the board by trying DFS from every cell with fresh visited array

for (int r = 0; r < rows; r++)Iterate over all rows as starting points

for (int c = 0; c < cols; c++)Iterate over all columns as starting points

boolean[][] visited = new boolean[rows][cols];Create a fresh visited array for each DFS to avoid contamination

if (dfs(board, word, r, c, 0, visited))If DFS finds the word starting at this cell, return true

private static boolean dfs(char[][] board, String word, int r, int c, int idx, boolean[][] visited)DFS helper to check if word exists starting at (r,c)

if (idx == word.length()) return true;Base case: all characters matched

visited[r][c] = true;Mark cell visited before recursive calls

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

for (String word : words)Check each word independently, leading to high time complexity

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

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

bool exist(vector<vector<char>>& board, string& word) {
    int rows = board.size(), cols = board[0].size();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            vector<vector<bool>> visited(rows, vector<bool>(cols, false));
            if (dfs(board, word, r, c, 0, visited))
                return true;
        }
    }
    return false;
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    vector<string> result;
    for (auto& word : words) {
        if (exist(board, word)) {
            result.push_back(word);
        }
    }
    return result;
}

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"};
    vector<string> res = findWords(board, words);
    for (auto& w : res) cout << w << " ";
    cout << endl;
    return 0;
}

Line Notes

bool dfs(vector<vector<char>>& board, string& word, int r, int c, int idx, vector<vector<bool>>& visited)DFS helper to check if word exists starting at (r,c)

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

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

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

for (int r = 0; r < rows; r++)Try all cells as starting points

for (int c = 0; c < cols; c++)Try all cells as starting points

vector<vector<bool>> visited(rows, vector<bool>(cols, false));Create fresh visited array for each DFS call

for (auto& word : words)Check each word independently

if (dfs(board, word, r, c, 0, visited))If DFS finds word, return true

function exist(board, word) {
    const rows = board.length, cols = board[0].length;

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

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            const visited = Array.from({length: rows}, () => Array(cols).fill(false));
            if (dfs(r, c, 0, visited)) return true;
        }
    }
    return false;
}

function findWords(board, words) {
    const result = [];
    for (const word of words) {
        if (exist(board, word)) {
            result.push(word);
        }
    }
    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 exist(board, word)Helper function to check if a single word exists

for (let r = 0; r < rows; r++)Try all rows as starting points

for (let c = 0; c < cols; c++)Try all columns as starting points

const visited = Array.from({length: rows}, () => Array(cols).fill(false));Create fresh visited array for each DFS call

if (dfs(r, c, 0, visited)) return true;If DFS finds the word starting at this cell, return true

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

if (idx === word.length) return true;Base case: all characters matched

visited[r][c] = true;Mark cell visited before recursive calls

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

for (const word of words)Check each word independently

⏱

Complexity

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

SpaceO(L) for recursion stack and visited array

For each word, we try starting from each cell and explore up to 4 directions recursively for length L, repeated for W words.

💡 For a 4x4 board and 10 words of length 5, this could mean millions of operations, which is impractical.

Interview Verdict: TLE / Use only to introduce problem and brute force concept

This approach is too slow for large inputs but is essential to understand before optimizing.

🧠

Backtracking with Trie for Prefix Pruning

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

Intuition

Build a prefix tree (Trie) of all words, then backtrack on the board, pruning paths that don't lead to any word in the Trie.

Algorithm

1. Build a Trie from the list of words.
2. For each cell in the board, start backtracking:
3. At each step, check if current prefix exists in Trie.
4. If prefix not in Trie, backtrack immediately (prune).
5. If a word ends at current Trie node, add it to result and mark as found.
6. Mark visited cells to avoid reuse and backtrack properly.

💡 The key is pruning early using Trie, which is not obvious initially but saves huge time.

</>

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 backtrack(r, c, parent):
            letter = board[r][c]
            currNode = parent.children.get(letter)
            if not currNode:
                return
            if currNode.word:
                result.append(currNode.word)
                currNode.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] != '#':
                    backtrack(nr, nc, currNode)
            board[r][c] = letter

            # Optimization: prune leaf nodes
            if not currNode.children:
                parent.children.pop(letter)

        for r in range(rows):
            for c in range(cols):
                backtrack(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:Defines Trie node structure with children and optional word

def buildTrie(self, words):Builds Trie from all words for prefix lookup

node.word = wMarks end of a word in Trie node

def backtrack(r, c, parent):Backtracking function exploring board with Trie pruning

currNode = parent.children.get(letter)Check if current letter continues a valid prefix

if currNode.word:Found a complete word, add to result and avoid duplicates

board[r][c] = '#'Mark cell visited to avoid reuse

board[r][c] = letterRestore cell after backtracking

if not currNode.children: parent.children.pop(letter)Prune leaf nodes to optimize Trie size during search

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

import java.util.*;

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

public class WordSearchTrie {
    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 backtrack(char[][] board, int r, int c, TrieNode parent, List<String> result) {
        char letter = board[r][c];
        TrieNode currNode = parent.children.get(letter);
        if (currNode == null) return;

        if (currNode.word != null) {
            result.add(currNode.word);
            currNode.word = null; // avoid duplicates
        }

        board[r][c] = '#';
        int[] rowOffsets = {1, -1, 0, 0};
        int[] colOffsets = {0, 0, 1, -1};
        for (int i = 0; i < 4; i++) {
            int nr = r + rowOffsets[i], nc = c + colOffsets[i];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && board[nr][nc] != '#') {
                backtrack(board, nr, nc, currNode, result);
            }
        }
        board[r][c] = letter;

        if (currNode.children.isEmpty()) {
            parent.children.remove(letter);
        }
    }

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

    public static void main(String[] args) {
        WordSearchTrie sol = new WordSearchTrie();
        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 {Defines Trie node with children map and optional word

TrieNode root = new TrieNode();Root of the Trie

node.children.putIfAbsent(c, new TrieNode());Insert character nodes if missing

if (currNode.word != null) {Found a complete word, add to result and avoid duplicates

board[r][c] = '#';Mark cell visited to prevent reuse

board[r][c] = letter;Restore cell after backtracking

if (currNode.children.isEmpty()) { parent.children.remove(letter); }Prune leaf nodes to optimize Trie

for (int r = 0; r < board.length; r++)Start backtracking from every cell

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

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

class Solution {
public:
    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 backtrack(vector<vector<char>>& board, int r, int c, TrieNode* parent, vector<string>& result) {
        char letter = board[r][c];
        if (!parent->children.count(letter)) return;
        TrieNode* currNode = parent->children[letter];

        if (!currNode->word.empty()) {
            result.push_back(currNode->word);
            currNode->word = ""; // avoid duplicates
        }

        board[r][c] = '#';
        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for (auto& d : directions) {
            int nr = r + d.first, nc = c + d.second;
            if (nr >= 0 && nr < board.size() && nc >= 0 && nc < board[0].size() && board[nr][nc] != '#') {
                backtrack(board, nr, nc, currNode, result);
            }
        }
        board[r][c] = letter;

        if (currNode->children.empty()) {
            parent->children.erase(letter);
            delete currNode;
        }
    }

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

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 optional word string

TrieNode* root = new TrieNode();Root node of Trie

if (!node->children.count(c))Insert new child node if missing

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

board[r][c] = '#';Mark cell visited to avoid reuse

board[r][c] = letter;Restore cell after backtracking

if (currNode->children.empty()) {Prune leaf nodes to optimize Trie size

for (int r = 0; r < board.size(); r++)Start backtracking from every cell

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

function 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;
}

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

    function backtrack(r, c, parent) {
        const letter = board[r][c];
        const currNode = parent.children.get(letter);
        if (!currNode) return;

        if (currNode.word !== null) {
            result.push(currNode.word);
            currNode.word = null; // avoid duplicates
        }

        board[r][c] = '#';
        const directions = [[1,0],[-1,0],[0,1],[0,-1]];
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
                backtrack(nr, nc, currNode);
            }
        }
        board[r][c] = letter;

        if (currNode.children.size === 0) {
            parent.children.delete(letter);
        }
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            backtrack(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 {Defines Trie node with children map and optional word

function buildTrie(words) {Builds Trie from words for prefix pruning

node.word = w;Marks end of a word in Trie

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

board[r][c] = '#';Mark cell visited to avoid reuse

board[r][c] = letter;Restore cell after backtracking

if (currNode.children.size === 0) { parent.children.delete(letter); }Prune leaf nodes to optimize Trie

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

⏱

Complexity

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

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

Trie pruning reduces search space drastically by cutting off invalid prefixes early, so not all paths are explored.

💡 For a 4x4 board and 10 words of length 5, this approach is much faster than brute force, often feasible in interviews.

Interview Verdict: Accepted / Optimal for large inputs

This is the standard efficient solution expected in interviews for this problem.

🧠

Backtracking with Trie + In-place Board Marking + Early Trie Pruning

💡 This approach is a refined version of the previous one, using in-place marking to save space and pruning Trie nodes aggressively to reduce search overhead.

Intuition

Mark visited cells directly on the board to avoid extra space, and remove Trie nodes when no longer needed to speed up future searches.

Algorithm

1. Build a Trie from the words.
2. For each cell, backtrack using the Trie:
3. Mark the board cell as visited by replacing with a special char.
4. If a word is found, add to result and remove from Trie.
5. After exploring neighbors, restore the cell.
6. Remove Trie nodes with no children to prune search space.

💡 In-place marking reduces memory usage and pruning keeps the Trie small, improving performance.

</>

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 backtrack(r, c, node):
            letter = board[r][c]
            currNode = node.children.get(letter)
            if not currNode:
                return
            if currNode.word:
                result.append(currNode.word)
                currNode.word = None

            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] != '#':
                    backtrack(nr, nc, currNode)
            board[r][c] = letter

            if not currNode.children:
                node.children.pop(letter)

        for r in range(rows):
            for c in range(cols):
                backtrack(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

board[r][c] = '#'In-place marking to save space instead of separate visited array

board[r][c] = letterRestore original letter after backtracking

if not currNode.children: node.children.pop(letter)Prune Trie nodes aggressively to reduce search space

currNode.word = NoneAvoid duplicate word additions

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

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

import java.util.*;

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

public class WordSearchTrieOptimized {
    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 backtrack(char[][] board, int r, int c, TrieNode node, List<String> result) {
        char letter = board[r][c];
        TrieNode currNode = node.children.get(letter);
        if (currNode == null) return;

        if (currNode.word != null) {
            result.add(currNode.word);
            currNode.word = null;
        }

        board[r][c] = '#';
        int[] rowOffsets = {1, -1, 0, 0};
        int[] colOffsets = {0, 0, 1, -1};
        for (int i = 0; i < 4; i++) {
            int nr = r + rowOffsets[i], nc = c + colOffsets[i];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && board[nr][nc] != '#') {
                backtrack(board, nr, nc, currNode, result);
            }
        }
        board[r][c] = letter;

        if (currNode.children.isEmpty()) {
            node.children.remove(letter);
        }
    }

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

    public static void main(String[] args) {
        WordSearchTrieOptimized sol = new WordSearchTrieOptimized();
        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

board[r][c] = '#'In-place marking to save space

board[r][c] = letter;Restore after backtracking

if (currNode.children.isEmpty()) { node.children.remove(letter); }Prune Trie nodes aggressively

currNode.word = null;Avoid duplicate word additions

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

for (int r = 0; r < board.length; r++)Start backtracking from every cell

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

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

class Solution {
public:
    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 backtrack(vector<vector<char>>& board, int r, int c, TrieNode* node, vector<string>& result) {
        char letter = board[r][c];
        if (!node->children.count(letter)) return;
        TrieNode* currNode = node->children[letter];

        if (!currNode->word.empty()) {
            result.push_back(currNode->word);
            currNode->word = "";
        }

        board[r][c] = '#';
        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for (auto& d : directions) {
            int nr = r + d.first, nc = c + d.second;
            if (nr >= 0 && nr < board.size() && nc >= 0 && nc < board[0].size() && board[nr][nc] != '#') {
                backtrack(board, nr, nc, currNode, result);
            }
        }
        board[r][c] = letter;

        if (currNode->children.empty()) {
            node->children.erase(letter);
            delete currNode;
        }
    }

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

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

board[r][c] = '#';In-place marking to save space

board[r][c] = letter;Restore after backtracking

if (currNode->children.empty()) {Prune Trie nodes aggressively

currNode->word = "";Avoid duplicate word additions

for (auto& d : directions)Explore all four directions

for (int r = 0; r < board.size(); r++)Start backtracking from every cell

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

function 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;
}

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

    function backtrack(r, c, node) {
        const letter = board[r][c];
        const currNode = node.children.get(letter);
        if (!currNode) return;

        if (currNode.word !== null) {
            result.push(currNode.word);
            currNode.word = null;
        }

        board[r][c] = '#';
        const directions = [[1,0],[-1,0],[0,1],[0,-1]];
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
                backtrack(nr, nc, currNode);
            }
        }
        board[r][c] = letter;

        if (currNode.children.size === 0) {
            node.children.delete(letter);
        }
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            backtrack(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

board[r][c] = '#';In-place marking to save space

board[r][c] = letter;Restore after backtracking

if (currNode.children.size === 0) { node.children.delete(letter); }Prune Trie nodes aggressively

currNode.word = null;Avoid duplicate word additions

for (const [dr, dc] of directions)Explore all four directions

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

⏱

Complexity

TimeO(M * 4 * 3^(L-1)) similar to previous approach but with less overhead

SpaceO(N) for Trie + O(L) recursion stack, less auxiliary space due to in-place marking

In-place marking and pruning reduce memory and runtime overhead, making it the most efficient practical approach.

💡 This approach is the best balance of speed and memory, ideal for interviews.

Interview Verdict: Accepted / Most optimal practical solution

This is the recommended approach to implement in interviews for best performance.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the Trie + backtracking approach with pruning in 95% of interviews for best balance of clarity and performance.

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)	N/A	Mention only - too slow to implement
2. Backtracking with Trie	O(M * 4 * 3^(L-1))	O(N) Trie + O(L) recursion stack	Yes	Yes	Optimal approach to implement
3. Backtracking with Trie + In-place Marking + Pruning	O(M * 4 * 3^(L-1)) with less overhead	O(N) Trie + O(L) recursion stack, less auxiliary space	Yes	Yes	Best practical solution to implement

💼

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 to show understanding.Step 3: Introduce Trie to optimize prefix checks and prune search.Step 4: Explain in-place marking and Trie pruning for best performance.Step 5: Code the optimal solution and test edge cases.

Time Allocation

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

What the Interviewer Tests

Ability to identify brute force limitations, knowledge of Trie data structure, backtracking skills, and optimization techniques.

Common Follow-ups

• How to handle very large word lists? → Use Trie and pruning to scale.
• Can diagonal moves be allowed? → Modify directions array accordingly.
• How to avoid duplicates in result? → Mark found words as null in Trie.
• What if board is very large? → Early pruning and iterative DFS can help.

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

🔍

Pattern Recognition

When to Use

1. Need to find multiple words in a grid 2. Words can be formed by adjacent letters 3. Large word list requiring efficient prefix checks 4. Backtracking with pruning is needed

Signature Phrases

find all wordsadjacent cellsprefix pruningbacktracking with Trie

NOT This Pattern When

Single word search without multiple words or no prefix pruning needed

Similar Problems

Word Search I - single word search in gridBoggle Game - similar grid word search with dictionaryImplement Trie (Prefix Tree) - foundational for pruning

Practice

1. You need to place n queens on an nxn chessboard so that no two queens threaten each other (no two queens share the same row, column, or diagonal). Which algorithmic approach guarantees finding all valid solutions efficiently by pruning invalid partial placements early?

easy

A. Backtracking with pruning to avoid columns and diagonals already attacked

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming to count valid queen placements using subproblems

D. Breadth-first search exploring all board states level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires placing queens so none attack each other, which involves checking columns and diagonals.

2. Step 2: Identify algorithm that prunes invalid states early

   Backtracking with pruning efficiently avoids exploring invalid partial solutions by tracking attacked columns and diagonals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking prunes invalid states early [OK]

Hint: Pruning columns and diagonals is key to efficient search [OK]

Common Mistakes:

• Thinking greedy placement always works
• Assuming DP applies directly
• Confusing BFS with pruning

2. Consider the following code snippet implementing the optimal backtracking solution for Word Search. Given the board = [["A","B","C"],["D","E","F"],["G","H","I"]] and word = "BEF", what is the return value of exist(board, word)?

easy

A. True

B. False

C. Raises IndexError

D. Infinite recursion

Solution

1. Step 1: Trace dfs starting at cell (0,1) 'B'

   Word starts with 'B', found at (0,1). dfs(0,1,0) matches 'B'.

2. Step 2: Explore neighbors for next chars 'E' and 'F'

   From (0,1), neighbors checked: (1,1) 'E' matches next char, then (1,2) 'F' matches last char. All matched, return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All characters found sequentially with valid moves [OK]

Hint: Trace dfs calls carefully to confirm path exists [OK]

Common Mistakes:

• Assuming no path due to adjacency confusion
• Missing in-place marking effect

3. What is the time complexity of the optimal backtracking solution for the Expression Add Operators problem, where n is the length of the input string? Assume the solution tries all operator insertions and substring splits with pruning and efficient string building.

medium

A. O(4^n) because at each position there are up to 4 choices (3 operators + no operator split)

B. O(n * 3^n) because each digit can be combined with 3 operators and substring splits

C. O(2^n) since only two operators are considered at each step

D. O(n^3) due to substring parsing and operator insertions

Solution

1. Step 1: Identify branching factor per digit

   At each digit, we can insert one of 3 operators (+, -, *) or choose to extend the current operand (no operator), but the main branching factor is 3 operators per split, and substring splits add a factor of n.

2. Step 2: Calculate total complexity

   The total complexity is roughly O(n * 3^n) because for each of the n positions, there are up to 3 operator choices, and substring splits add an n factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential branching with 3 operators and substring splits [OK]

Hint: 3 operators per digit and substring splits lead to O(n * 3^n) complexity [OK]

Common Mistakes:

• Confusing substring parsing cost as cubic
• Assuming only 2 operators reduce complexity
• Miscounting branching factor as 4

4. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            # Bug: missing leading zero check
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

medium

A. Line with 'if i != index and num[index] == '0':' missing here

B. Line with 'curr_str = num[index:i+1]' (substring extraction)

C. Line with 'path[length_before:] = []' (backtracking cleanup)

D. Line with 'path.append('+'); path.append(curr_str)' (operator insertion)

Solution

1. Step 1: Identify handling of leading zeros

   The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".

2. Step 2: Confirm bug location

   This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check causes invalid operands [OK]

Hint: Leading zero check missing causes invalid operands [OK]

Common Mistakes:

• Confusing backtracking cleanup lines as bug
• Thinking substring extraction is buggy

5. What is the time complexity of generating all permutations of an array of length n using Heap's algorithm, and why might a common misconception about this complexity be incorrect?

medium

A. O(n! * n^2) because each permutation requires n swaps and there are n! permutations

B. O(n! * log n) because Heap's algorithm uses a heap data structure internally

C. O(n! * n) because each of the n! permutations requires copying the array of length n

D. O(n! + n) because generating permutations is factorial plus linear overhead

Solution

1. Step 1: Identify number of permutations

   There are n! permutations for an array of length n.

2. Step 2: Analyze cost per permutation

   Heap's algorithm generates each permutation with O(1) swaps, but copying the current permutation to the result list takes O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time complexity is O(n! * n) due to copying each permutation [OK]

Hint: Copying each permutation costs O(n), not the swaps themselves [OK]

Common Mistakes:

• Assuming swaps cost O(n) each or confusing heap data structure usage