212. Word Search II - Solution & Explanation

Q: Is Word Search II easy or hard?

Word Search II is classified as Hard because it requires combining Trie construction with DFS backtracking and pruning. A naive search easily leads to exponential exploration, while the optimal solution reduces work by sharing prefix paths.

Q: Word Search II Python/Java solution

Python and Java implementations usually create a Trie node class with children pointers and a flag for completed words. DFS explores the board while moving through the Trie simultaneously. When a node marks the end of a word, it gets added to the result set.

Q: How to solve Word Search II in O(n)?

An O(n) solution is not possible because the algorithm must explore multiple paths in the grid. The optimal practical approach is Trie-based backtracking, which prunes invalid prefixes early and significantly reduces the search space compared with checking each word separately.

Q: What is the best approach for Word Search II?

The most efficient approach builds a Trie from all words and performs DFS backtracking on the board. The Trie allows prefix pruning so the search stops immediately when a path cannot form any word. This avoids repeating work for shared prefixes and is the expected interview solution.

Q: Is Word Search II asked at Google/Amazon/Meta?

Word Search II appears frequently in interviews at companies like Amazon, Google, and Meta because it combines multiple concepts: Trie data structures, DFS backtracking, and grid traversal. Interviewers use it to evaluate pruning strategies and recursive search optimization.

Q: What data structure is used in Word Search II?

The key data structure is a Trie (prefix tree). It stores all dictionary words so DFS exploration can quickly determine whether the current path forms a valid prefix or complete word. The board traversal itself uses backtracking with a visited state.

Q: What is the time complexity of Word Search II?

The Trie + backtracking solution runs in O(m * n * 4^L) time in the worst case, where m and n are board dimensions and L is the maximum word length. Space complexity is O(N) for storing the Trie, where N is the total number of characters across all words.

The problem

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

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

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 10⁴
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Approach overview

Problem Overview: You get an m x n board of characters and a list of words. A word can be formed by moving horizontally or vertically across adjacent cells without reusing the same cell in one path. The task is to return every word from the list that exists in the grid.

Approach 1: Backtracking and HashSet (O(W * m * n * 4^L) time, O(L) space)

This approach treats each word independently. For every word in the dictionary, start a DFS from every board cell that matches the first character. Use backtracking to explore four directions (up, down, left, right) while marking cells as visited so they are not reused in the same path. If the DFS successfully matches all characters of the word, add it to a result HashSet to avoid duplicates. The main drawback is repeated work: many prefixes overlap between words, yet the search restarts from scratch for each one. The worst‑case time complexity becomes O(W * m * n * 4^L), where W is the number of words and L is the maximum word length. Space complexity is O(L) for the recursion stack.

This method is straightforward and easy to implement, but it becomes slow when the word list is large because the board is scanned repeatedly for similar prefixes.

Approach 2: Backtracking with Trie (O(m * n * 4^L) time, O(N) space)

The optimized approach builds a Trie from the list of words before exploring the grid. A Trie stores shared prefixes, so multiple words that begin with the same characters reuse the same search path. Start DFS from each cell in the board, but only continue exploring if the current prefix exists in the Trie. If a Trie node marks the end of a word, add that word to the result immediately.

This pruning drastically reduces unnecessary exploration. If the board path forms a prefix that doesn't exist in the Trie, the search stops early. Each DFS step checks a child node in the Trie, which is an O(1) lookup. The search still explores up to four directions per step, leading to worst‑case complexity O(m * n * 4^L), but in practice it is much faster due to prefix pruning. Space complexity is O(N) for the Trie, where N is the total number of characters across all words.

This technique combines backtracking with a Trie to efficiently share prefix searches. The board traversal itself is a typical matrix DFS problem.

Recommended for interviews: Interviewers expect the Trie + backtracking solution. The HashSet approach demonstrates understanding of DFS search on a grid, but it repeats work for overlapping prefixes. Using a Trie shows that you can optimize prefix searches and reduce redundant exploration, which is the key insight for this problem.

Approach 1: Using Backtracking with Trie

This approach uses a Trie to represent the list of words for efficient prefix matching. The algorithm performs depth-first search (DFS) on the board starting from each cell. Each path of exploration is checked against the Trie to determine if it forms any of the words or prefixes thereof. The benefit of using a Trie is that we can stop the search early if the current path does not match any prefix in the Trie, thereby improving the efficiency of the search process.

Python

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

class Solution:
    def __init__(self):
        self.result = set()

    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
        for i in range(len(board)):
            for j in range(len(board[0])):
                self._dfs(board, i, j, root)
        return list(self.result)

    def _dfs(self, board, i, j, node):
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return
        char = board[i][j]
        if char == '#' or char not in node.children:
            return
        node = node.children[char]
        if node.word:
            self.result.add(node.word)
        board[i][j] = '#'
        self._dfs(board, i + 1, j, node)
        self._dfs(board, i - 1, j, node)
        self._dfs(board, i, j + 1, node)
        self._dfs(board, i, j - 1, node)
        board[i][j] = char

Java

import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

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

public class Solution {
    private void insertWord(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.word = word;
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            insertWord(root, word);
        }
        Set<String> result = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }
        return new ArrayList<>(result);
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, Set<String> result) {
        char c = board[i][j];
        if (c == '#' || node.children[c - 'a'] == null) return;
        node = node.children[c - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null;
        }

        board[i][j] = '#';
        if (i > 0) dfs(board, i-1, j, node, result);
        if (j > 0) dfs(board, i, j-1, node, result);
        if (i < board.length - 1) dfs(board, i+1, j, node, result);
        if (j < board[0].length - 1) dfs(board, i, j+1, node, result);
        board[i][j] = c;
    }
}

C++

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

class TrieNode {
public:
    vector<TrieNode*> children;
    string word;
    TrieNode() : children(26, nullptr), word("") {}
};

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

    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, unordered_set<string>& result) {
        char ch = board[i][j];
        if (ch == '#' || !node->children[ch - 'a']) return;
        node = node->children[ch - 'a'];
        if (!node->word.empty()) {
            result.insert(node->word);
            node->word.clear(); // Avoid duplicates
        }

        board[i][j] = '#'; // Mark visited
        if (i > 0) dfs(board, i - 1, j, node, result);
        if (j > 0) dfs(board, i, j - 1, node, result);
        if (i < board.size() - 1) dfs(board, i + 1, j, node, result);
        if (j < board[0].size() - 1) dfs(board, i, j + 1, node, result);
        board[i][j] = ch; // Reset
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (const string& word : words) {
            insertWord(root, word);
        }

        unordered_set<string> result;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, root, result);
            }
        }
        return vector<string>(result.begin(), result.end());
    }
};

JavaScript

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

function insertWord(root, word) {
    let node = root;
    for (const char of word) {
        if (!node.children.has(char)) {
            node.children.set(char, new TrieNode());
        }
        node = node.children.get(char);
    }
    node.word = word;
}

function findWords(board, words) {
    const root = new TrieNode();
    for (const word of words) insertWord(root, word);
    const result = new Set();

    const dfs = (i, j, node) => {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;

        const char = board[i][j];
        if (char === '#' || !node.children.has(char)) return;

        node = node.children.get(char);
        if (node.word) {
            result.add(node.word);
            node.word = null; // Avoid duplicates
        }

        board[i][j] = '#';
        dfs(i + 1, j, node);
        dfs(i - 1, j, node);
        dfs(i, j + 1, node);
        dfs(i, j - 1, node);
        board[i][j] = char;
    };

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            dfs(i, j, root);
        }
    }

    return Array.from(result);
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    char* word;
} TrieNode;

TrieNode* createTrieNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL;
    node->word = NULL;
    return node;
}

void insertWord(TrieNode* root, char* word) {
    TrieNode* node = root;
    while (*word) {
        if (!node->children[*word - 'a'])
            node->children[*word - 'a'] = createTrieNode();
        node = node->children[*word - 'a'];
        word++;
    }
    node->word = strdup(word);
}

void findWordsDFS(char** board, int i, int j, int m, int n, TrieNode* node, bool** visited, char** result, int* returnSize) {
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || !node->children[board[i][j] - 'a'])
        return;

    node = node->children[board[i][j] - 'a'];
    if (node->word) {
        result[*returnSize] = strdup(node->word);
        (*returnSize)++;
        node->word = NULL; // Avoid duplicate printing
    }

    visited[i][j] = true;
    findWordsDFS(board, i + 1, j, m, n, node, visited, result, returnSize);
    findWordsDFS(board, i - 1, j, m, n, node, visited, result, returnSize);
    findWordsDFS(board, i, j + 1, m, n, node, visited, result, returnSize);
    findWordsDFS(board, i, j - 1, m, n, node, visited, result, returnSize);
    visited[i][j] = false;
}

char** findWords(char** board, int boardSize, int* boardColSize, char** words, int wordsSize, int* returnSize) {
    TrieNode* root = createTrieNode();
    for (int i = 0; i < wordsSize; i++)
        insertWord(root, words[i]);

    *returnSize = 0;
    char** result = (char**)malloc(1000 * sizeof(char*)); // Assumption on max result size
    bool** visited = (bool**)malloc(boardSize * sizeof(bool*));
    for (int i = 0; i < boardSize; i++)
        visited[i] = (bool*)calloc(*boardColSize, sizeof(bool));

    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < *boardColSize; j++) {
            findWordsDFS(board, i, j, boardSize, *boardColSize, root, visited, result, returnSize);
        }
    }

    // Free visited array
    for (int i = 0; i < boardSize; i++)
        free(visited[i]);
    free(visited);

    return result;
}

using System;
using System.Collections.Generic;

public class TrieNode {
    public TrieNode[] Children = new TrieNode[26];
    public string Word;
}

public class Solution {
    public IList<string> FindWords(char[][] board, string[] words) {
        TrieNode root = new TrieNode();
        foreach (var word in words) InsertWord(root, word);
        HashSet<string> result = new HashSet<string>();
        for (int i = 0; i < board.Length; i++)
            for (int j = 0; j < board[0].Length; j++)
                Dfs(board, i, j, root, result);
        return new List<string>(result);
    }

    private void InsertWord(TrieNode root, string word) {
        TrieNode node = root;
        foreach (var ch in word) {
            if (node.Children[ch - 'a'] == null)
                node.Children[ch - 'a'] = new TrieNode();
            node = node.Children[ch - 'a'];
        }
        node.Word = word;
    }

    private void Dfs(char[][] board, int i, int j, TrieNode node, HashSet<string> result) {
        char c = board[i][j];
        if (c == '#' || node.Children[c - 'a'] == null) return;
        node = node.Children[c - 'a'];
        if (node.Word != null) {
            result.Add(node.Word);
            node.Word = null; // Avoid duplicates
        }

        board[i][j] = '#';
        if (i > 0) Dfs(board, i - 1, j, node, result);
        if (j > 0) Dfs(board, i, j - 1, node, result);
        if (i < board.Length - 1) Dfs(board, i + 1, j, node, result);
        if (j < board[0].Length - 1) Dfs(board, i, j + 1, node, result);
        board[i][j] = c;
    }
}

This Python solution constructs a Trie with the input words and explores the board using DFS starting from each cell. It keeps track of words found using a result set, ensuring no duplicates in the output.

Complexity

Time Complexity: O(M*(4*3^(L-1))), where M is the number of cells on the board, and L is the maximum length of a word.
Space Complexity: O(N*L), where N is the number of words, and L is the maximum length of a word, used by the Trie structure.

Try this approach in the editor

Approach 2: Using Backtracking and HashSet

In this approach, we perform backtracking for each word individually. This avoids the overhead of constructing a Trie but involves repeated board scanning. A Recursive Depth First Search (DFS) is used to explore possibilities starting from each cell on the board. We maintain a visited matrix to ensure a letter is not reused in forming a particular word.

Python

class Solution:
    def exist(self, board, word):
        def dfs(i, j, index):
            if index == len(word):
                return True
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
                return False
            if board[i][j] != word[index]:
                return False
            tmp, board[i][j] = board[i][j], '#'  # mark visited
            found = (dfs(i+1, j, index+1) or
                     dfs(i-1, j, index+1) or
                     dfs(i, j+1, index+1) or
                     dfs(i, j-1, index+1))
            board[i][j] = tmp  # unmark visited
            return found

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False

Java

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(board, word, i, j, 0, new boolean[board.length][board[0].length])) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        if (index == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length) return false;
        if (visited[i][j] || board[i][j] != word.charAt(index)) return false;

        visited[i][j] = true;
        if (dfs(board, word, i + 1, j, index + 1, visited) ||
            dfs(board, word, i - 1, j, index + 1, visited) ||
            dfs(board, word, i, j + 1, index + 1, visited) ||
            dfs(board, word, i, j - 1, index + 1, visited)) {
            return true;
        }
        visited[i][j] = false;
        return false;
    }
}

C++

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

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (dfs(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, string& word, int index, int i, int j, vector<vector<bool>>& visited) {
        if (index == word.length()) return true;
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return false;
        if (visited[i][j] || board[i][j] != word[index]) return false;

        visited[i][j] = true;
        if (dfs(board, word, index + 1, i + 1, j, visited) ||
            dfs(board, word, index + 1, i - 1, j, visited) ||
            dfs(board, word, index + 1, i, j + 1, visited) ||
            dfs(board, word, index + 1, i, j - 1, visited)) {
            return true;
        }
        visited[i][j] = false;
        return false;
    }
};

JavaScript

function exist(board, word) {
    function dfs(i, j, index) {
        if (index === word.length) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        if (board[i][j] !== word[index]) return false;
        let temp = board[i][j];
        board[i][j] = '#';
        let found = dfs(i+1, j, index+1) ||
                    dfs(i-1, j, index+1) ||
                    dfs(i, j+1, index+1) ||
                    dfs(i, j-1, index+1);
        board[i][j] = temp;
        return found;
    }

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    return false;
}

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool dfs(char** board, int boardSize, int boardColSize, char* word, int index, int i, int j, bool** visited) {
    if (index == strlen(word)) return true;
    if (i < 0 || i >= boardSize || j < 0 || j >= boardColSize || visited[i][j] || board[i][j] != word[index])
        return false;

    visited[i][j] = true;
    if (dfs(board, boardSize, boardColSize, word, index + 1, i - 1, j, visited) ||
        dfs(board, boardSize, boardColSize, word, index + 1, i + 1, j, visited) ||
        dfs(board, boardSize, boardColSize, word, index + 1, i, j - 1, visited) ||
        dfs(board, boardSize, boardColSize, word, index + 1, i, j + 1, visited)) {
        return true;
    }
    visited[i][j] = false;
    return false;
}

bool exist(char** board, int boardSize, int* boardColSize, char* word) {
    bool** visited = (bool**)malloc(boardSize * sizeof(bool*));
    for (int i = 0; i < boardSize; i++) {
        visited[i] = (bool*)calloc(*boardColSize, sizeof(bool));
    }
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < *boardColSize; j++) {
            if (dfs(board, boardSize, *boardColSize, word, 0, i, j, visited)) {
                for (int k = 0; k < boardSize; k++){
                    free(visited[k]);
                }
                free(visited);
                return true;
            }
        }
    }
    for (int i = 0; i < boardSize; i++){
        free(visited[i]);
    }
    free(visited);
    return false;
}

public class Solution {
    public bool Exist(char[][] board, string word) {
        for (int i = 0; i < board.Length; i++) {
            for (int j = 0; j < board[0].Length; j++) {
                if (Dfs(board, word, i, j, 0, new bool[board.Length, board[0].Length])) {
                    return true;
                }
            }
        }
        return false;
    }

    private bool Dfs(char[][] board, string word, int i, int j, int index, bool[,] visited) {
        if (index == word.Length) return true;
        if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length) return false;
        if (visited[i, j] || board[i][j] != word[index]) return false;

        visited[i, j] = true;
        if (Dfs(board, word, i + 1, j, index + 1, visited) ||
            Dfs(board, word, i - 1, j, index + 1, visited) ||
            Dfs(board, word, i, j + 1, index + 1, visited) ||
            Dfs(board, word, i, j - 1, index + 1, visited)) {
            return true;
        }
        visited[i, j] = false;
        return false;
    }
}

In this Python version, the dfs function tries to match each character in the word on the board. By marking visited nodes with a temporary replacement, it facilitates recursion without repeating nodes within the same word search.

Complexity

Time Complexity: O(N * M * 3^L), where N is the number of words, M is the number of cells in the board, and L is the length of the word being searched in the worst case.
Space Complexity: O(L), for the recursive call stack.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

class Trie {
    children: Trie[];
    ref: number;

    constructor() {
        this.children = new Array(26);
        this.ref = -1;
    }

    insert(w: string, ref: number): void {
        let node: Trie = this;
        for (let i = 0; i < w.length; i++) {
            const c = w.charCodeAt(i) - 97;
            if (node.children[c] == null) {
                node.children[c] = new Trie();
            }
            node = node.children[c];
        }
        node.ref = ref;
    }
}

function findWords(board: string[][], words: string[]): string[] {
    const tree = new Trie();
    for (let i = 0; i < words.length; ++i) {
        tree.insert(words[i], i);
    }
    const m = board.length;
    const n = board[0].length;
    const ans: string[] = [];
    const dirs: number[] = [-1, 0, 1, 0, -1];
    const dfs = (node: Trie, i: number, j: number) => {
        const idx = board[i][j].charCodeAt(0) - 97;
        if (node.children[idx] == null) {
            return;
        }
        node = node.children[idx];
        if (node.ref != -1) {
            ans.push(words[node.ref]);
            node.ref = -1;
        }
        const c = board[i][j];
        board[i][j] = '#';
        for (let k = 0; k < 4; ++k) {
            const x = i + dirs[k];
            const y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '#') {
                dfs(node, x, y);
            }
        }
        board[i][j] = c;
    };
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            dfs(tree, i, j);
        }
    }
    return ans;
}

type Trie struct {
	children [26]*Trie
	ref      int
}

func newTrie() *Trie {
	return &Trie{ref: -1}
}
func (this *Trie) insert(w string, ref int) {
	node := this
	for _, c := range w {
		c -= 'a'
		if node.children[c] == nil {
			node.children[c] = newTrie()
		}
		node = node.children[c]
	}
	node.ref = ref
}

func findWords(board [][]byte, words []string) (ans []string) {
	trie := newTrie()
	for i, w := range words {
		trie.insert(w, i)
	}
	m, n := len(board), len(board[0])
	var dfs func(*Trie, int, int)
	dfs = func(node *Trie, i, j int) {
		idx := board[i][j] - 'a'
		if node.children[idx] == nil {
			return
		}
		node = node.children[idx]
		if node.ref != -1 {
			ans = append(ans, words[node.ref])
			node.ref = -1
		}
		c := board[i][j]
		board[i][j] = '#'
		dirs := [5]int{-1, 0, 1, 0, -1}
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '#' {
				dfs(node, x, y)
			}
		}
		board[i][j] = c
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			dfs(trie, i, j)
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Backtracking with Trie	Time Complexity: O(M(43^(L-1))), where M is the number of cells on the board, and L is the maximum length of a word. Space Complexity: O(N*L), where N is the number of words, and L is the maximum length of a word, used by the Trie structure.
Using Backtracking and HashSet	Time Complexity: O(N * M * 3^L), where N is the number of words, M is the number of cells in the board, and L is the length of the word being searched in the worst case. Space Complexity: O(L), for the recursive call stack.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking and HashSet	O(W * m * n * 4^L)	O(L)	Small word lists or when implementing a simple DFS per word
Backtracking with Trie	O(m * n * 4^L)	O(N)	Best general solution when many words share prefixes

Frequently asked questions

Is Word Search II easy or hard?

Word Search II is classified as Hard because it requires combining Trie construction with DFS backtracking and pruning. A naive search easily leads to exponential exploration, while the optimal solution reduces work by sharing prefix paths.

Word Search II Python/Java solution

Python and Java implementations usually create a Trie node class with children pointers and a flag for completed words. DFS explores the board while moving through the Trie simultaneously. When a node marks the end of a word, it gets added to the result set.

How to solve Word Search II in O(n)?

An O(n) solution is not possible because the algorithm must explore multiple paths in the grid. The optimal practical approach is Trie-based backtracking, which prunes invalid prefixes early and significantly reduces the search space compared with checking each word separately.

What is the best approach for Word Search II?

The most efficient approach builds a Trie from all words and performs DFS backtracking on the board. The Trie allows prefix pruning so the search stops immediately when a path cannot form any word. This avoids repeating work for shared prefixes and is the expected interview solution.

Is Word Search II asked at Google/Amazon/Meta?

Word Search II appears frequently in interviews at companies like Amazon, Google, and Meta because it combines multiple concepts: Trie data structures, DFS backtracking, and grid traversal. Interviewers use it to evaluate pruning strategies and recursive search optimization.

What data structure is used in Word Search II?

The key data structure is a Trie (prefix tree). It stores all dictionary words so DFS exploration can quickly determine whether the current path forms a valid prefix or complete word. The board traversal itself uses backtracking with a visited state.

What is the time complexity of Word Search II?

The Trie + backtracking solution runs in O(m * n * 4^L) time in the worst case, where m and n are board dimensions and L is the maximum word length. Space complexity is O(N) for storing the Trie, where N is the total number of characters across all words.

Word Search II solution and explanation

The problem

Approach overview

Approach 1: Using Backtracking with Trie

Approach 2: Using Backtracking and HashSet

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Word Search II solution and explanation

The problem

Approach overview

Approach 1: Using Backtracking with Trie

Approach 2: Using Backtracking and HashSet

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems