Leetcode - 211. Design Add and Search Words Data Structure

🔎 Word Dictionary with Wildcards — Trie + DFS Approach

Imagine you’re building a search engine for words where users can type queries with wildcards like "c.t" and it should match "cat", "cot", or "cut". This problem is essentially LeetCode 211: Design Add and Search Words Data Structure, and it’s a perfect use case for Tries + DFS.

---

💡 Problem Recap

We need a data structure that can:

1. Add words efficiently (like "apple", "bat", "ball")
2. Search words where queries may contain "." as a wildcard, matching any single character.

Example:

addWord("cat");
addWord("car");
search("cat"); // true
search("c.t"); // true (matches "cat" or "cot" if present)
search("dog"); // false

---

🧠 Approach

1. Why Trie?

A Trie (prefix tree) is a natural fit here:

• Each node represents a character.
• You can quickly traverse the structure when searching.
• Supports fast prefix/wildcard lookups.

2. Handling . (wildcards)

Normally in a Trie, you check one path for the exact character.
But when you see ".", it can mean any character. So instead of one path, we must try all child nodes at that level (DFS recursion helps here).

---

📝 Implementation

Here’s the clean, working solution in JavaScript:

var WordDictionary = function () {
    this.root = {};
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
    let node = this.root;

    for (let letter of word) {
        if (!node[letter]) {
            node[letter] = {};
        }
        node = node[letter];
    }
    node.wordEnd = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
    const dfs = (node, idx) => {
        if (idx === word.length) return node.wordEnd === true;

        let ch = word[idx];
        if (ch === ".") {
            for (let key in node) {
                if (key !== "wordEnd" && dfs(node[key], idx + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            if (!node[ch]) return false;
            return dfs(node[ch], idx + 1);
        }
    }
    return dfs(this.root, 0);
};

---

⚖️ Complexity Analysis

• Add Word:
  Each word is inserted character by character → O(L), where L is word length.

• Search Word:

  • Best case (no wildcards): O(L)
  • Worst case (lots of "."): branching factor × word length → O(26^L) in the extreme worst case, but usually much less in practice.

---

🌍 Real-World Scenarios

1. Search Engines / Autocomplete

• Imagine typing "d.g" into Google, it could suggest "dog", "dig", "dug".
• Tries are widely used in search suggestions because they allow efficient prefix/wildcard lookups.

1. Spell Checkers

• When checking misspelled words, "c.t" can match "cat" or "cut". This is useful for autocorrect systems.

1. Crossword Puzzles & Word Games (like Scrabble)

• Players often search words with missing letters. A Trie with wildcards makes this super efficient.

1. Security Applications

• Matching patterns in logs or network requests (e.g., "p.ssword" to detect attempts at password variations).

---

🎯 Final Thoughts

This problem shows the real power of Tries + DFS when handling flexible string search. It’s more than a coding exercise — it’s a pattern that powers Google search suggestions, IDE autocompletes, crossword solvers, and even intrusion detection systems.

So next time you type "c.t" into your favorite word puzzle app and it magically gives "cat", "cot", and "cut", you know what’s working behind the scenes.

---