Word Search - Practice Coding Problems

Word Search - Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can 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.

Input & Output

Example 1 — Found Word

$ Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

› Output: true

💡 Note: Path exists: A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1). Each step moves to adjacent cell without reusing.

Example 2 — Word Not Found

$ Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

› Output: false

💡 Note: Cannot form ABCB because after A(0,0) → B(0,1) → C(0,2), we need another B but the original B(0,1) cannot be reused.

Example 3 — Single Character

$ Input: board = [["A"]], word = "A"

› Output: true

💡 Note: Single cell matches single character word perfectly.

Constraints

m == board.length
n = board[i].length
1 ≤ m, n ≤ 6
1 ≤ word.length ≤ 15
board and word consists of only lowercase and uppercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Grid of characters and target word ABCCED

Try each cell as start, explore 4 directions with backtracking

Result

Return true if valid path found, false otherwise

Key Takeaway

🎯 Key Insight: Use DFS with backtracking to explore all possible paths while preventing cell reuse through temporary marking

Asked in

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

The key insight is to use backtracking DFS from each cell, marking visited cells and unmarking during backtrack. Optimizations include character frequency pre-check and starting from less frequent character end. Best approach uses DFS with backtracking. Time: O(m × n × 4^L), Space: O(L)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Backtracking	O(m × n × 4^L)	O(L)	Efficient DFS with early termination and path pruning
Brute Force with DFS	O(m × n × 4^L)	O(L)	Try every cell as starting point and explore all directions

Optimized Backtracking — Algorithm Steps

Pre-check: verify all word characters exist in grid
For each matching starting cell, begin DFS exploration
Use backtracking with visited marking and early termination

Visualization

Tap to expand

Step-by-Step Walkthrough

Precheck

Verify all word characters exist in sufficient quantities

Smart Start

Begin from less frequent character end

Efficient DFS

Explore with early termination and backtracking

Code -

solution.c — C

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

bool dfs(char** board, int boardSize, int* boardColSize, char* word, int r, int c, int index, int wordLen) {
    if (index == wordLen) return true;
    
    if (r < 0 || r >= boardSize || c < 0 || c >= boardColSize[r] || 
        board[r][c] != word[index]) {
        return false;
    }
    
    char temp = board[r][c];
    board[r][c] = '#';
    
    bool found = dfs(board, boardSize, boardColSize, word, r+1, c, index+1, wordLen) ||
                dfs(board, boardSize, boardColSize, word, r-1, c, index+1, wordLen) ||
                dfs(board, boardSize, boardColSize, word, r, c+1, index+1, wordLen) ||
                dfs(board, boardSize, boardColSize, word, r, c-1, index+1, wordLen);
    
    board[r][c] = temp;
    return found;
}

bool solution(char** board, int boardSize, int* boardColSize, char* word) {
    if (boardSize == 0 || boardColSize[0] == 0 || strlen(word) == 0) return false;
    
    int wordLen = strlen(word);
    
    // Simple character frequency check
    int boardChars[256] = {0};
    int wordChars[256] = {0};
    
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            boardChars[(int)board[i][j]]++;
        }
    }
    
    for (int i = 0; i < wordLen; i++) {
        wordChars[(int)word[i]]++;
    }
    
    for (int i = 0; i < 256; i++) {
        if (wordChars[i] > boardChars[i]) return false;
    }
    
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            if (board[i][j] == word[0] && 
                dfs(board, boardSize, boardColSize, word, i, j, 0, wordLen)) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char word[100];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    // Simple parsing for demo
    char** board = malloc(10 * sizeof(char*));
    int* boardColSize = malloc(10 * sizeof(int));
    int boardSize = 3;
    
    for (int i = 0; i < boardSize; i++) {
        board[i] = malloc(10 * sizeof(char));
        boardColSize[i] = 4;
    }
    
    strcpy(board[0], "ABCE");
    strcpy(board[1], "SFCS");
    strcpy(board[2], "ADEE");
    
    bool result = solution(board, boardSize, boardColSize, word);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × 4^L)

Same worst case but with optimizations that reduce average case significantly

✓ Linear Growth

Space Complexity

O(L)

Recursion stack depth plus character frequency map

✓ Linear Space

89.2K Views

High Frequency

~25 min Avg. Time

2.8K 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 Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler