Word Search II - Practice Coding Problems

Word Search II - Problem

Array String Backtracking Trie Matrix Hard

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.

Input & Output

Example 1 — Basic Word Search

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

💡 Note: "eat" can be formed: e(1,0)→a(1,2)→t(1,1). "oath" can be formed: o(0,0)→a(0,1)→t(1,1)→h(2,1). "pea" and "rain" cannot be formed on this board.

Example 2 — Single Character Board

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

› Output: []

💡 Note: "abcb" cannot be formed because we cannot reuse the same cell. After a→b→c, we cannot go back to use 'b' again.

Example 3 — Multiple Short Words

$ Input: board = [["a","a"]], words = ["a","aa","aaa"]

› Output: ["a","aa"]

💡 Note: "a" can be formed using either cell. "aa" can be formed using both cells a(0,0)→a(0,1). "aaa" cannot be formed as we only have 2 'a' characters.

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

Visualization

Tap to expand

Understanding the Visualization

Input

2D board of characters and list of target words

Process

Search for each word using DFS with backtracking on adjacent cells

Output

List of all words found on the board

Key Takeaway

🎯 Key Insight: Use Trie data structure to eliminate redundant prefix searches and enable efficient multi-word detection in a single traversal

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is using a Trie (prefix tree) to eliminate redundant prefix searches and enable early termination when no valid word prefixes exist. Best approach combines Trie construction with DFS backtracking for optimal performance. Time: O(M × N × 4^L), Space: O(W × L)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Trie + Backtracking	O(M × N × 4^L + W × L)	O(W × L)	Build a Trie from words, then use DFS with Trie traversal for efficient search
Brute Force - Individual Word Search	O(W × M × N × 4^L)	O(L)	Search for each word individually using DFS backtracking

Optimized Trie + Backtracking — Algorithm Steps

Step 1: Build Trie from all words
Step 2: DFS from each board cell while traversing Trie
Step 3: When reaching Trie word end, add to results and continue

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Construct prefix tree from all target words

DFS + Trie

Single traversal following both board paths and Trie paths

Collect Words

When reaching word end in Trie, add to results

Code -

solution.c — C

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

#define ALPHABET_SIZE 26

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

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

void dfs(char** board, int m, int n, int i, int j, TrieNode* node, char*** result, int* returnSize) {
    if (i < 0 || i >= m || j < 0 || j >= n) return;
    
    char c = board[i][j];
    if (c == '#' || !node->children[c - 'a']) return;
    
    node = node->children[c - 'a'];
    if (node->word) {
        (*result)[*returnSize] = malloc(strlen(node->word) + 1);
        strcpy((*result)[*returnSize], node->word);
        (*returnSize)++;
        node->word = NULL; // Avoid duplicates
    }
    
    board[i][j] = '#';
    dfs(board, m, n, i + 1, j, node, result, returnSize);
    dfs(board, m, n, i - 1, j, node, result, returnSize);
    dfs(board, m, n, i, j + 1, node, result, returnSize);
    dfs(board, m, n, i, j - 1, node, result, returnSize);
    board[i][j] = c;
}

char** solution(char** board, int boardSize, int* boardColSize, char** words, int wordsSize, int* returnSize) {
    *returnSize = 0;
    TrieNode* root = createNode();
    
    // Build Trie
    for (int i = 0; i < wordsSize; i++) {
        TrieNode* node = root;
        for (int j = 0; words[i][j]; j++) {
            int index = words[i][j] - 'a';
            if (!node->children[index]) {
                node->children[index] = createNode();
            }
            node = node->children[index];
        }
        node->word = malloc(strlen(words[i]) + 1);
        strcpy(node->word, words[i]);
    }
    
    char** result = malloc(wordsSize * sizeof(char*));
    
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            dfs(board, boardSize, boardColSize[i], i, j, root, &result, returnSize);
        }
    }
    
    return result;
}

int main() {
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(M × N × 4^L + W × L)

M×N starting positions × 4^L DFS paths + W×L to build Trie

✓ Linear Growth

Space Complexity

O(W × L)

Trie stores all words (W words × L average length)

✓ Linear Space

186.5K Views

High Frequency

~35 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Trie + Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler