Word Search Ii - 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 CURRENT_CELL = 'current_cell', CURRENT_CELL_COLOR = 'blue';
const CURRENT_TRIE_NODE = 'current_trie_node', CURRENT_TRIE_NODE_COLOR = 'orange';
const NEXT_NEIGHBOUR = 'next_neighbour', NEXT_NEIGHBOUR_COLOR = 'gold';

class TrieNode {
    constructor() {
        this.children = new VisChildrenObject();
        this.wordIndex = null; // Store word index at end node instead of full word
    }
}

function visMainFunction(boardInput, words) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    const board = new VisArray2D(...boardInput.map(row => new VisArray(...row))).options({ label: 'Board' });
    const root = new TrieNode();
    const tree = new VisDictionaryTree(root, { dataPropName: 'wordIndex' });

    buildTrie(words, root);

    const result = new VisArray();
    const rows = board.length;
    const cols = board[0].length;

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            startPartialBatch();
            setCurrentTrieNode(root, tree);
            setCurrentCell(row, col, board);
            notification(`🔍 Starting DFS from ${makeColoredSpan('board cell', CURRENT_CELL_COLOR)} at [${row},${col}] containing letter <b>${board[row][col]}</b>.`);
            endBatch();

            dfs(row, col, root);
        }
    }

    notification(`🏁 <b>Search Complete!</b> Words found: <b>${result.join(', ')}</b>.`);
    return result;

    function buildTrie(words, root) {
        notification(`📂 <b>Building the Trie</b> to store all dictionary words by their indices for efficient prefix matching.`);
        for (let wordIndex = 0; wordIndex < words.length; wordIndex++) {
            const word = words[wordIndex];
            startPartialBatch();
            notification(`✏️ <b>Inserting word:</b> <b>${word}</b> (index ${wordIndex}) into the Trie.`);
            let node = root;
            for (const char of word) {
                if (!node.children[char]) {
                    notification(`➕ No child for <b>${char}</b> at ${makeColoredSpan('current trie node', CURRENT_TRIE_NODE_COLOR)}. Creating a new node for <b>${char}</b> and proceeding to it.`);
                    node.children[char] = new TrieNode();
                } else {
                    notification(`➡️ Child for <b>${char}</b> already exists. Moving to the corresponding ${makeColoredSpan('trie node', CURRENT_TRIE_NODE_COLOR)}.`);
                }
                node = node.children[char];
            }
            notification(`🏁 Reached the end of <b>${word}</b>. Storing its <b>index (${wordIndex})</b> at the ${makeColoredSpan('current trie node', CURRENT_TRIE_NODE_COLOR)} since the path from root to this node yields the full word.`);
            node.wordIndex = wordIndex;
            endBatch();
        }
    }

    function dfs(row, col, node) {
        const char = board[row][col];

        startPartialBatch();
        setCurrentCell(row, col, board);
        notification(`
            🔎 Exploring ${makeColoredSpan('board cell', CURRENT_CELL_COLOR)} at [${row},${col}] with letter <b>${char}</b>.  
            Checking whether this letter can extend the <b>current Trie prefix</b>.
        `);
        
        node = node.children[char];

        if (!node) {
            notification(`
                ❌ No matching child found for <b>${char}</b> in the ${makeColoredSpan('current trie node', CURRENT_TRIE_NODE_COLOR)}.  
                This prefix does not exist in the dictionary — <b>pruning</b> this DFS path.
            `);
            endBatch();
            return;
        }

        notification(`
            ✅ Found a matching child for <b>${char}</b> in the Trie.  
            Proceeding to this child by assigning the ${makeColoredSpan('current trie node', CURRENT_TRIE_NODE_COLOR)} to it.
        `);
        setCurrentTrieNode(node, tree);

        if (node.wordIndex !== null) {
            const foundWord = words[node.wordIndex];
            notification(`
                ✅ Found a complete word: <b>${foundWord}</b> (index ${node.wordIndex}) ending at the current DFS path.  
                Adding it to the result list.
            `);
            result.push(foundWord);
            notification(`
                🧹 Clearing this word index stored at the ${makeColoredSpan('current trie node', CURRENT_TRIE_NODE_COLOR)}  
                (by assigning it to <code>null</code>) to avoid counting duplicates from other paths.
            `);
            node.wordIndex = null; // Prevent duplicates
        }

        notification(`
            🔒 Temporarily marking ${makeColoredSpan('current board cell', CURRENT_CELL_COLOR)} at [${row},${col}] as visited (<b>#</b>)  
            so it cannot be reused within this DFS path. Exploring its valid neighbors next.
        `);
        board[row][col] = '#'; // Mark visited
        endBatch();

        const directions = [
            [0, 1],  // Right
            [1, 0],  // Down
            [0, -1], // Left
            [-1, 0]  // Up
        ];

        for (const [dx, dy] of directions) {
            const newRow = row + dx;
            const newCol = col + dy;
            if (
                newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                board[newRow][newCol] !== '#'
            ) {
                startPartialBatch();
                setCurrentCell(row, col, board);
                setCurrentTrieNode(node, tree);
                const boardVm = board.makeVisManagerForIndexPair(newRow, newCol).addClass(NEXT_NEIGHBOUR);
                notification(`🔄 Exploring ${makeColoredSpan('neighbor cell', NEXT_NEIGHBOUR_COLOR)} at [${newRow},${newCol}] from ${makeColoredSpan('current cell', CURRENT_CELL_COLOR)} at [${row},${col}].`);
                boardVm.removeClass(NEXT_NEIGHBOUR);
                endBatch();
                dfs(newRow, newCol, node);
            }
        }

        startPartialBatch();
        board[row][col] = char; // Restore original letter
        notification(`
            ↩️ Finished exploring all neighbors of ${makeColoredSpan('current cell', CURRENT_CELL_COLOR)} at [${row},${col}].  
            Restored its original letter <b>${char}</b> to make it available again for future DFS explorations.
        `);
        endBatch();
    }
}

// --- Visual helpers ---
let currentCellVM = null;
let currentTrieVM = null;

function setCurrentCell(row, col, board) {
    startBatch();
    currentCellVM && currentCellVM.removeClass(CURRENT_CELL);
    currentCellVM = board.makeVisManagerForIndexPair(row, col).addClass(CURRENT_CELL);
    endBatch();
}

function setCurrentTrieNode(node, tree) {
    startBatch();
    currentTrieVM && currentTrieVM.removeClass(CURRENT_TRIE_NODE);
    currentTrieVM = tree.makeVisManagerForNode(node).addClass(CURRENT_TRIE_NODE);
    endBatch();
}

function initClassProperties() {
    setClassProperties(CURRENT_CELL, { borderColor: CURRENT_CELL_COLOR });
    setClassProperties(NEXT_NEIGHBOUR, { backgroundColor: NEXT_NEIGHBOUR_COLOR });
    setClassProperties(CURRENT_TRIE_NODE, { borderColor: CURRENT_TRIE_NODE_COLOR });
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        <b>🎨 Visual Cues (Color Schema)</b>
        <ul>
            <li>
                ${makeColoredSpan('Current board cell', CURRENT_CELL_COLOR)} — 
                ${CURRENT_CELL_COLOR} border on the board cell currently being explored in the DFS path.
            </li>
            <li>
                ${makeColoredSpan('Current trie node', CURRENT_TRIE_NODE_COLOR)} — 
                ${CURRENT_TRIE_NODE_COLOR} border on the Trie node representing the prefix formed so far
                by the path on the board.
            </li>
            <li>
                ${makeColoredSpan('Neighbor cell candidate', NEXT_NEIGHBOUR_COLOR)} — 
                ${NEXT_NEIGHBOUR_COLOR} background temporarily highlights a neighboring cell that is being
                considered as the next DFS step from the current cell.
            </li>
        </ul>
    `);
}

Approach

We combine a Trie (prefix tree) with DFS backtracking on the board to efficiently find all words. Instead of storing full words at Trie nodes, we store their indices in the original words array. This avoids redundant string storage while still enabling fast lookup, and simplifying duplicate handling by clearing the stored index at a node once its corresponding word is found.

🧱 Trie Construction

Each TrieNode contains:
- children: maps each character to the next TrieNode, forming the links that build word paths through the Trie.
- wordIndex: initially null; set to the index of a word in the words array when a complete word ends at this node.
For each word words[i]:
- Walk from the root, creating child nodes as needed for each character.
- At the final node, set node.wordIndex = i, meaning: “the path from root to this node exactly spells words[i]”.

🔍 DFS on the Board + Trie

We iterate over every cell [row, col] of the board and start a DFS from there.
At each DFS step:
- Use the current board character to move along the Trie via children[char]. If no matching child exists, this path cannot form any word → prune immediately.
- If the resulting Trie node has wordIndex !== null, we have matched a full word:
  - Retrieve it as words[wordIndex] and add it to the result list.
  - Set wordIndex = null on that node to avoid counting the same word again from other paths (this handles duplicates cleanly).
- Mark the current board cell as visited by setting it to '#' so it cannot be reused in the same path.
- Recurse into up to 4 neighbors (up, down, left, right) that are inside bounds and not '#'.
- After exploring all neighbors, restore the original character in the cell to make it available again for future DFS explorations.

🧠 Why Index Storage?

Avoid copying full strings into Trie nodes.
Directly map a terminal node back to words[wordIndex] when a match is found.
Can “consume” a found word by setting wordIndex = null, preventing duplicates in a simple, constant-time way.

Time Complexity

Let N be the total number of cells in the board, K be the total number of characters across all inserted words, and L be the maximum word length.

Building the Trie: O(K) — each character from every word is processed once, resulting in a total cost proportional to the sum of all word lengths.
DFS traversal: O(N × 3^L) in the worst case — we start a DFS from every cell (N), and each search can branch to up to 4 directions initially, but to at most 3 directions afterward since we never revisit the previous cell.

Overall time complexity: O(K + N × 3^L), where O(K) comes from Trie construction and O(N × 3^L) from DFS explorations.

Space Complexity

Let K be the total number of characters across all inserted words, and L be the maximum word length.

Trie storage: O(K) — each unique prefix is stored once across all words. In the worst case (when no prefixes are shared), every character requires a new node, resulting in O(K) nodes in total.
DFS recursion stack: O(L) — the maximum call depth equals the length of the longest word since each recursive call represents one character in the current search path.

Overall space complexity: O(K), since L cannot exceed K.

Input-1

Word Search Ii - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🧱 Trie Construction

🔍 DFS on the Board + Trie

🧠 Why Index Storage?

Time Complexity

Space Complexity