✅ Trie + DFS | ✅ Easy Code
IntuitionThe problem requires us to implement a dictionary where we can check if modifying exactly one character in a search word can match any word in the dict
# Intuition
The problem requires us to implement a dictionary where we can check if modifying exactly one character in a search word can match any word in the dictionary. A **Trie** (Prefix Tree) is an ideal data structure for this because it allows us to efficiently store words and perform character-based searches.

# Approach
1. **Trie Construction:**  
   - We create a `MagicDictionary` class with a root Trie node.
   - Each node contains an array of pointers to child nodes (representing 26 lowercase English letters) and a boolean `end` to mark word completion.
   - The `buildDict` function inserts each word into the Trie.

2. **Search with One Modification:**  
   - The `search` function performs a **DFS traversal** over the Trie.
   - At each step, we either:
     - Follow the exact character match (if it's present).
     - Try replacing it with any other letter (only if no replacement has been made before).
   - If we reach the end of a word in the Trie with exactly one change, we return `true`.

# Complexity
- **Time Complexity:**
  - **Insertion:** $$O(n \cdot k)$$, where $$n$$ is the number of words and $$k$$ is the average word length.
  - **Search:** $$O(k \cdot 26)$$, since for each character in the search word, we iterate over at most 26 possibilities.

- **Space Complexity:** $$O(n \cdot k)$$ to store all words in the Trie.

# Code
```cpp
struct Node {
    Node* links[26] = {NULL};
    bool end = false;

    bool contain(char ch) {
        return links[ch - 'a'] != NULL;
    }

    void put(char ch, Node* node) {
        links[ch - 'a'] = node;
    }

    Node* get(char ch) {
        return links[ch - 'a'];
    }

    bool isEnd() {
        return end;
    }

    void setEnd() {
        end = true;
    }
};

class MagicDictionary {
public:
    Node* root;

    MagicDictionary() {
        root = new Node();
    }

    void insert(string& s) {
        Node* node = root;
        for (char c : s) {
            if (!node->contain(c)) {
                node->put(c, new Node());
            }
            node = node->get(c);
        }
        node->setEnd();
    }

    void buildDict(vector<string> dictionary) {
        for (auto& word : dictionary) {
            insert(word);
        }
    }

    bool dfs(Node* node, string& word, int index, bool changed) {
        if (!node) return false;
        if (index == word.size()) return changed && node->isEnd();

        char curr = word[index];
        for (char c = 'a'; c <= 'z'; c++) {
            if (node->contain(c)) {
                
                if (c == curr) {
                    if (dfs(node->get(c), word, index + 1, changed)) {
                        return true;
                    }
                } else if (!changed) {
                    if (dfs(node->get(c), word, index + 1, true)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool search(string searchWord) {
        return dfs(root, searchWord, 0, false);
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */
```


['Depth-First Search', 'Trie', 'C++']