Design Add and Search Words Data Structure - 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 = 'current', CURRENT_COLOR = 'blue';
const FOUND = 'found', FOUND_COLOR = 'green';
const NOT_FOUND = 'not_found', NOT_FOUND_COLOR = 'red';
const WILDCARD_BRANCH = 'wildcard_branch', WILDCARD_BRANCH_COLOR = 'gray';

class TrieNode {
    constructor() {
        this.children = new VisChildrenObject(); 
        this.isEndOfWord = false;
    }
}

class WordDictionary {
    constructor() {
        this.root = new TrieNode();
        this.tree = new VisDictionaryTree(this.root, { dataPropName: 'isEndOfWord' }).options({
            labelExtractionPolicy: d => (d === true ? 'END' : ''),
        }).createVis();
    }

    addWord(word) {
        let node = this.root;

        startPartialBatch();
        const wordVis = new VisArray(...word).options({ label: 'word' });
        let index = 0;
        makeVisVariable(index).registerAsIndexPointer(wordVis, CURRENT);
        setCurrentNode(node, this.tree);
        notification(`✏️ <b>Adding word:</b> <b>${word}</b> to the dictionary.`);
        endBatch();

        for (const char of word) {
            startPartialBatch();
            if (!node.children[char]) {
                notification(`➕ No child for <b>${char}</b> found at ${makeColoredSpan('current node', CURRENT_COLOR)}. Creating and moving to it.`);
                node.children[char] = new TrieNode();
            } else {
                notification(`➡️ Child node for <b>${char}</b> exists at ${makeColoredSpan('current node', CURRENT_COLOR)}. Moving to it.`);
            }
            node = node.children[char];
            setCurrentNode(node, this.tree);
            index += 1;
            endBatch();
        }

        startPartialBatch();
        node.isEndOfWord = true;
        notification(`✅ Marked ${makeColoredSpan('current node', CURRENT_COLOR)} as ${makeColoredSpan('end of word', FOUND_COLOR)} — completed insertion of <b>${word}</b>.`);
        endBatch();
    }

    search(word) {
        notification(`
            🔍 <b>Searching</b> for "<b>${word}</b>": each normal character must match a child edge exactly,  
            and wildcard (<b>.</b>) may match <b>any single character</b>. The path must end at a node marked as ${makeColoredSpan('end of word', FOUND_COLOR)}.
        `);
        const wordVis = new VisArray(...word).options({ label: 'word' });
        const result = this._searchFromNode(word, this.root, 0, wordVis);
        notification(result ? `✅ Word <b>${word}</b> found in the dictionary.` : `❌ Word <b>${word}</b> not found in the dictionary.`);
        wordVis.destroyVis();
        return result;
    }

    // Note that the wordVis parameter is not part of the original algorithm but just used for visualization
    _searchFromNode(word, node, startIndex, wordVis) {
        if (!node) return false;

        for (let index = startIndex; index < word.length; index++) {
            let char = word[index];
            startPartialBatch();
            setCurrentNode(node, this.tree);
            setCurrentIndex(index, wordVis);

            if (char === '.') {
                notification(`
                    🔄 Wildcard (<b>.</b>) encountered at <b>index ${index}</b>:  
                    <b>.</b> can match <i>any</i> character here, so we must try <b>all children</b> of the
                    ${makeColoredSpan('current node', CURRENT_COLOR)} and continue recursively from each branch.
                `);
                endBatch();

                for (const child in node.children) {
                    startPartialBatch();
                    const childVm = this.tree.makeVisManagerForNode(node.children[child]);
                    childVm.addClass(WILDCARD_BRANCH);
                    notification(`↪️ Exploring ${makeColoredSpan(`child '${child}'`, WILDCARD_BRANCH_COLOR)} as a possible match for the wildcard position.`);
                    endBatch();

                    if (this._searchFromNode(word, node.children[child], index + 1, wordVis)) {
                        childVm.removeClass(WILDCARD_BRANCH);
                        return true;
                    }
                    childVm.removeClass(WILDCARD_BRANCH);
                }

                notification(`❌ All wildcard branches from this position were explored — none led to a valid word match.`);
                return false;
            } else if (!node.children[char]) {
                notification(`❌ <b>Path not found:</b> no child for <b>${char}</b> from the ${makeColoredSpan('current node', CURRENT_COLOR)} — search failed here.`);
                endBatch();
                return false;
            } else {
                notification(`➡️ Moving from ${makeColoredSpan('current node', CURRENT_COLOR)} to its child for <b>${char}</b>.`);
                node = node.children[char];
                endBatch();
            }
        }

        startPartialBatch();
        setCurrentNode(node, this.tree);
        setCurrentIndex(-1, wordVis);

        const found = node.isEndOfWord;
        const statusClass = found ? FOUND : NOT_FOUND;
        const vm = this.tree.makeVisManagerForNode(node);
        vm.addClass(statusClass);
        notification(found
            ? `✅ Reached ${makeColoredSpan('current node', CURRENT_COLOR)} which is marked as ${makeColoredSpan('end of word', FOUND_COLOR)} — this is a <b>valid full match</b>.`
            : `❌ Reached ${makeColoredSpan('current node', CURRENT_COLOR)} which is <b>not</b> marked as ${makeColoredSpan('end of word', FOUND_COLOR)} — this path is only a <b>prefix</b>, not a complete word.`
        );
        vm.removeClass(statusClass);
        endBatch();
        return found;
    }
}

function visMainFunction(operations, args) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    let dict = null;
    const results = [];

    for (let i = 0; i < operations.length; i++) {
        const op = operations[i];
        const arg = args[i][0]; // single string arg

        if (op === 'WordDictionary') {
            notification(`🚀 Initializing the Word Dictionary.`);
            dict = new WordDictionary();
            results.push(null);
        } else if (op === 'addWord') {
            // startBatch();
            dict.addWord(arg);
            results.push(null);
            // endBatch();
        } else if (op === 'search') {
            const res = dict.search(arg);
            results.push(res);
        }
    }
    return results;
}

// --- Visual helpers ---

let currentNode = null;

function setCurrentNode(node, tree) {
    if (node === currentNode) return;
    startBatch();
    currentNode && tree.makeVisManagerForNode(currentNode).removeClass(CURRENT);
    node && tree.makeVisManagerForNode(node).addClass(CURRENT);
    currentNode = node;
    endBatch();
}

let currIndex = -1;
function setCurrentIndex(index, visArr) {
    if (index === currIndex) return;
    startBatch();
    (currIndex >= 0 && currIndex < visArr.length) && visArr.makeVisManagerForIndex(currIndex).removeClass(CURRENT);
    (index >= 0 && index < visArr.length) && visArr.makeVisManagerForIndex(index).addClass(CURRENT);
    currIndex = index;
    endBatch();
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(FOUND, { backgroundColor: FOUND_COLOR });
    setClassProperties(NOT_FOUND, { backgroundColor: NOT_FOUND_COLOR });
    setClassProperties(WILDCARD_BRANCH, { backgroundColor: WILDCARD_BRANCH_COLOR });
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    <b>🎨 Visual Cues (Color Schema)</b>
    <ul>
      <li>${makeColoredSpan('Current', CURRENT_COLOR)} — ${CURRENT_COLOR} border for the <b>current node</b> being processed or the <b>current character</b> in the word/pattern.</li>
      <li>${makeColoredSpan('Found node', FOUND_COLOR)} — ${FOUND_COLOR} background when the search ends successfully on a complete word (<code>isEndOfWord = true</code>).</li>
      <li>${makeColoredSpan('Not found node', NOT_FOUND_COLOR)} — ${NOT_FOUND_COLOR} background when traversal ends but the node is <b>not</b> marked as an end-of-word.</li>
      <li>${makeColoredSpan('Wildcard branch', WILDCARD_BRANCH_COLOR)} — ${WILDCARD_BRANCH_COLOR} background while exploring multiple branches due to a wildcard (<b>.</b>).</li>
    </ul>
  `);
}

Approach

We implement a Trie-based dictionary that supports two operations: addWord(word) and search(word), where '.' can match any single character.

🧱 Trie Structure

Each node is a TrieNode with:
- children: keeps track of all possible next nodes — each entry represents a character leading to the next step along a word’s path.
- isEndOfWord: true if a complete word ends at this node.
Words are stored character by character along a path from the root, and shared prefixes reuse the same nodes.

✏️ addWord(word)

Start from root.
For each character c in word:
- If children[c] does not exist, create a new TrieNode.
- Move down to children[c].
After all characters are processed, mark the final node’s isEndOfWord = true.
This ensures the entire word is stored in the Trie as a path starting from the root and ending at an end-of-word node.

🔍 search(word) with '.' Wildcards

The helper _searchFromNode(word, node, index) examines the substring word[index..] starting from the given node. The main search begins with a call to _searchFromNode(word, root, 0), meaning it starts from the root node and the first character of the word. Inside the helper, a loop runs from the current index up to the end of the word, processing one character per step:

If the character is a wildcard ('.'):
- '.' can match any single character at this position.
- We iterate through all children of the current node and recursively call _searchFromNode(word, child, index + 1) for each of them.
- If any recursive call returns true, we propagate true upward immediately.
- If none succeed, return false.
Else if there is no child for the current character:
- The path breaks — return false since the required child does not exist.
Else (child exists for the current character):
- Move down to that child node and continue the loop with index + 1.

Once the loop finishes (i.e., index === word.length), we return the isEndOfWord flag of the current (terminal) node. It directly indicates whether the search ended on a complete word or only on a prefix.

🧠 Correctness Intuition

The Trie constrains the search to only those paths that match the query: normal characters follow a single exact child edge, while '.' triggers a controlled branching over all possible next characters at that position. By recursively exploring every valid continuation for wildcard positions and requiring the final node to be marked with isEndOfWord = true, any true result corresponds to an actual stored word that matches the pattern exactly.

Time Complexity

Let L be the length of the input word or search pattern.

addWord(word): O(L) — visiting one node per character, creating a new node only if it does not already exist.
search(word): O(L).

Although wildcard ('.') matching can in theory cause branching at each occurrence, here the number of wildcards is strictly limited (at most two per query). Each wildcard can substitute for any of the 26 lowercase letters, so at most 26 × 26 alternative paths are explored when both appear. This branching factor is a constant with respect to the word length. For each normal character, the algorithm linearly proceeds to the corresponding child (or stops traversal if the child is missing). Therefore, the maximum total number of visited nodes scales linearly with L.

Space Complexity

Let M be the total number of characters across all added words, and L the length of a single inserted word.

addWord(word): O(L) — in the worst case, a new node is created for each character if no prefix is shared with existing words.
Overall Trie storage: O(M) — total number of nodes across all inserted words, worst case happens when there is no shared prefix at all.

Each node contains a children mapping and a boolean flag isEndOfWord. These structures are constant in size per node, so they do not affect the asymptotic complexity.

Input-1

Design Add and Search Words Data Structure - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🧱 Trie Structure

✏️ addWord(word)

🔍 search(word) with '.' Wildcards

🧠 Correctness Intuition

Time Complexity

Space Complexity