Word Search - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const MATCH = 'match', MATCH_COLOR = 'green';
const MISMATCH = 'mismatch', MISMATCH_COLOR = 'red';

function visMainFunction(inputBoard, inputWord) {
    if (!inputBoard.length || !inputBoard[0].length) {
        notification(`❌ <b>Invalid Input:</b> The board is empty.`);
        return false;
    }

    initClassProperties();
    explanationAndColorPaletteNotifications();

    const numRows = inputBoard.length;
    const numCols = inputBoard[0].length;

    startPartialBatch();
    const board = new VisArray2D(...(inputBoard.map(row => new VisArray(...row)))).options({ label: 'Board' });
    const word = new VisArray(...inputWord);
    notification(`🔎 <b>Scanning the board</b> — trying each cell in the board as a potential starting point for forming the word <b>"${inputWord}"</b> through backtracking.`);
    endBatch();

    for (let rowIndex = 0; rowIndex < numRows; rowIndex++) {
        for (let colIndex = 0; colIndex < numCols; colIndex++) {
            notification(`▶️ <b>Attempt:</b> starting backtracking at cell (<b>${rowIndex}</b>, <b>${colIndex}</b>) to match <b>"${inputWord}"</b> from index <b>0</b>.`);
            if (backtrack(board, word, rowIndex, colIndex, 0, numRows, numCols)) {
                notification(`✅ <b>Success!</b> The word <b>"${inputWord}"</b> was found in the board.`);
                return true;
            }
        }
    }

    notification(`❌ <b>Failed!</b> The word <b>"${inputWord}"</b> does not exist in the board.`);
    return false;
}

function backtrack(board, word, rowIndex, colIndex, wordIndex, numRows, numCols) {
    if (wordIndex === word.length) {
        notification(`✅ <b>Word Complete!</b> Successfully matched all ${word.length} characters.`);
        return true;
    }

    if (
        rowIndex < 0 || colIndex < 0 ||
        rowIndex >= numRows || colIndex >= numCols
    ) {
        return false;
    }

    if (word[wordIndex] !== board[rowIndex][colIndex]) {
        handleMismatch(board, word, rowIndex, colIndex, wordIndex);
        return false;
    }

    startPartialBatch();
    handleMatch(board, word, rowIndex, colIndex, wordIndex);

    // Mark cell as visited
    board[rowIndex][colIndex] = "#";
    endBatch();

    // Explore all possible directions (Down, Up, Right, Left)
    const found = backtrack(board, word, rowIndex + 1, colIndex, wordIndex + 1, numRows, numCols) || 
                  backtrack(board, word, rowIndex - 1, colIndex, wordIndex + 1, numRows, numCols) || 
                  backtrack(board, word, rowIndex, colIndex + 1, wordIndex + 1, numRows, numCols) ||
                  backtrack(board, word, rowIndex, colIndex - 1, wordIndex + 1, numRows, numCols);

    if (!found) {
        startPartialBatch();
        // Restore the original character if this path didn't work
        notification(`🔙 <b>Backtracking:</b> Restoring '${word[wordIndex]}' at (${rowIndex}, ${colIndex}).`);
        board[rowIndex][colIndex] = word[wordIndex];

        word.makeVisManagerForIndex(wordIndex).removeClass(MATCH);
        board.makeVisManagerForIndexPair(rowIndex, colIndex).removeClass(MATCH);
        endBatch();
    }

    return found;
}

function initClassProperties() {
    setClassProperties(MATCH, { backgroundColor: MATCH_COLOR });
    setClassProperties(MISMATCH, { backgroundColor: MISMATCH_COLOR });
}

function handleMismatch(board, word, rowIndex, colIndex, wordIndex) {
    startPartialBatch();
    const wordCharVisManager = word.makeVisManagerForIndex(wordIndex);
    const boardCellVisManager = board.makeVisManagerForIndexPair(rowIndex, colIndex);

    wordCharVisManager.addClass(MISMATCH);
    boardCellVisManager.addClass(MISMATCH);
    notification(`❌ <b>${makeColoredSpan('Mismatch', MISMATCH_COLOR)}: </b> 
        <br> - <b>Position:</b> (${rowIndex}, ${colIndex})
        <br> - <b>Expected:</b> '${word[wordIndex]}'
        <br> - <b>Found:</b> ${makeColoredSpan("'" + board[rowIndex][colIndex] + "'", MISMATCH_COLOR)}`);
    boardCellVisManager.removeClass(MISMATCH);
    wordCharVisManager.removeClass(MISMATCH);

    endBatch();
}

function handleMatch(board, word, rowIndex, colIndex, wordIndex) {
    word.makeVisManagerForIndex(wordIndex).addClass(MATCH);
    board.makeVisManagerForIndexPair(rowIndex, colIndex).addClass(MATCH);
    notification(`✅ <b>${makeColoredSpan(`Matched '${word[wordIndex]}'`, MATCH_COLOR)}</b> at (<b>${rowIndex}</b>, <b>${colIndex}</b>). <br>
        🧩 We now <b>mark this cell as visited</b> by temporarily setting 
        <code>board[${rowIndex}][${colIndex}] = "#"</code> — this prevents revisiting the same cell in the current path, 
        avoiding cycles during backtracking. <br>
        🔍 After marking, the algorithm will <b>explore all four possible directions</b> — down, up, right, and left — 
        to continue matching the remaining characters of the word from this position.`);
}

function explanationAndColorPaletteNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Legend</b>
        <ul>
        <li>
            <b>${makeColoredSpan('Green background', MATCH_COLOR)}</b> (<code>${MATCH}</code>):  
            Indicates a <b>successful character match</b> between the current board cell and the corresponding letter in the word.  
            Once matched, the cell is <b>temporarily marked as visited</b> (set to <code>"#"</code>) to prevent revisiting it in the current path.
        </li>
        <li>
            <b>${makeColoredSpan('Red background', MISMATCH_COLOR)}</b> (<code>${MISMATCH}</code>):  
            Highlights a <b>mismatch</b> — when the current board cell does not match the expected letter of the word.
        </li>
        <li>
            Together, these colors visualize the <b>decision process of backtracking</b>:  
            green cells show the active search path, while red flashes mark dead ends that trigger backtracking.
        </li>
        </ul>
    `);
}

Approach

We determine whether the word exists by performing a depth-first search (DFS) with backtracking from every cell in the board. From each starting position, we attempt to match the target word character by character, moving one step at a time in the four cardinal directions (down, up, right, left) without revisiting any cell in the same path.

Start from every cell:
Iterate over all (rowIndex, colIndex) positions. For each cell, start a DFS backtracking search to form the entire word beginning at that cell (with wordIndex = 0). If any DFS call matches all characters, return true immediately.
Recursive function (backtrack): The function backtrack(board, word, rowIndex, colIndex, wordIndex) attempts to match the remaining part of the word starting from wordIndex, beginning the search from the cell at (rowIndex, colIndex) on the board.
- ✅ Base case: If wordIndex === word.length, the entire word is matched — return true.
- 🚫 Boundary / mismatch check: If the cell is out of bounds or board[rowIndex][colIndex] !== word[wordIndex] (which also covers cases where the cell was already marked as visited with "#"), this path fails — return false.
Mark → Explore → Restore:
- Mark as visited: Temporarily set board[rowIndex][colIndex] = "#" to prevent revisiting the same cell in the current exploration path, avoiding cycles.
- Explore four directions: Recurse to each neighboring cell — down, up, right, and left — passing wordIndex + 1 as the new wordIndex parameter. This advances the search to the next character of the word after a successful match, continuing the path in all possible directions.
- Backtrack (restore): If none of the recursive calls succeed, restore the original character before returning false, allowing the cell to be used again in other paths.
Why this works:
- Each recursive call explores all valid continuations of the current prefix.
- Marking visited cells prevents infinite loops or reuse of a cell in one path.
- Restoring the character ensures correctness for later explorations.
- By starting from every cell, we cover all possible placements of the word on the board.
Result: If any DFS path returns true, the word exists in the board. Otherwise, after all starting positions are tested without finding a complete match, the result is false.

Time Complexity

Let m and n be the board dimensions and L be the word length. The worst-case running time is O(m · n · 3^L).

Starting points: We may start a DFS from any of the m · n cells.
Branching factor: At the first character there are at most 4 choices (up/down/left/right). After moving once, you cannot immediately return to the previous cell, leaving at most 3 choices per subsequent step.
Depth: The search depth is the word length L, yielding ≈ 4 × 3^L−1 paths per start. This is asymptotically O(3^L) per start.

Combining both factors gives O(m · n · 3^L).

Space Complexity

The algorithm uses O(L) auxiliary space, where L is the length of the target word.

Recursion stack: Each recursive DFS call corresponds to one character of the word, leading to a maximum recursion depth of L.
In-place marking: The board itself is modified temporarily (by setting visited cells to "#"), so no extra visited matrix is required.

Hence, the overall auxiliary space complexity is O(L).

Input-1

Input-2

Word Search - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity