[C++] Trie || DFS || O(N) || Easy to Read
Explanation:\n\nHow to Implement Trie ?\n\nCheck this problem: 208 Implement Trie (Prefix Tree)Link\n\n\nContinue....\n\nPattern = Variation of Trie.\n\n- Inser
**Explanation:**\n\nHow to Implement Trie ?\n\nCheck this problem: 208 Implement Trie (Prefix Tree)[Link](https://leetcode.com/problems/implement-trie-prefix-tree/)\n\n\nContinue....\n\nPattern = Variation of Trie.\n\n- Insert is same.\n\n- In search, we must perform one mismatch. Same word can not return true.\n\n    Example.. "hello" -> "hello" return false.\n              "hello" -> "hallo" return true.\n\nWe perform the Trie Traversal with DFS(for one mismatch).\n\nCheck the below code.\n\n\n```\n// Trie Node.\nstruct Node {\n\n    Node* links[26];\n    bool endOfWord = false;\n\n    void put(char ch, Node* node) {\n        links[ch-\'a\'] = node;\n    }\n\n    Node* get(char ch) {\n        return links[ch-\'a\'];\n    }\n\n    bool contains(char ch) {\n        return links[ch-\'a\'] != NULL;\n    }\n\n    void setEndOfWord() {\n        endOfWord = true;\n    }\n\n    bool isEndOfWord() {\n        return endOfWord;\n    }\n};\n\n\n\nclass MagicDictionary {\n\npublic:\n\n    MagicDictionary() {\n        // Initialize the root node.\n        root = new Node();\n    }\n    \n    void buildDict(vector<string> dictionary) {\n\n        // Add all the words into trie.\n        for(string word: dictionary){\n            insert(word);\n        }\n    }\n    \n    bool searchSupport(string s, int index, Node* node, bool allowedOnce) {\n        \n        // Base case. Found NULL, It can not be EndOfWord.\n        if(node == NULL)\n            return false;\n\n\n        for(int i = index; i < s.size(); i++) {\n            \n            // allowedOnce is set then we try all characters for current s[i].\n            if(allowedOnce) {\n\n                for(char p = \'a\'; p <= \'z\'; p++) {\n                        \n                    // allowedOnce is depend, s[i] and p is same or not.\n                    // If same, then allowedOnce = true else false.\n                    if(searchSupport(s, i+1, node->get(p), s[i]==p)) {\n                        return true;\n                    }\n                }\n\n                // Try all characters but did not find the end of word. Return false.\n                return false;\n            }\n                \n            // allowedOnce = false, then node must contains s[i].\n            if(!node->contains(s[i]))\n                return false;\n\n            // Move to next Node.\n            node = node->get(s[i]);\n        }\n        \n        // node is EndOfWord and allowedOnce == false(one mismatch) then we return true.\n        if(node != NULL && !allowedOnce && node->isEndOfWord())\n            return true;\n\n        return false;\n    }\n\n\n    bool search(string searchWord) {\n        return searchSupport(searchWord, 0, root, true);\n    }\n\nprivate:\n\n    Node* root;\n\n    void insert(string word) {\n        Node* node = root;\n        for(char ch: word) {\n            if(!node->contains(ch)) {\n                node->put(ch, new Node());\n            }\n            node = node->get(ch);\n        }\n        node->setEndOfWord();\n    }\n\n};\n\n```\n\n\n**Approach and Time Complexity:**\n\nN = number of words\nL = length of word\nk = 26\n\n1) Trie\nTime: O(N*L*K) = O(N) [L and K is constant]\nSpace: O(N*L) = O(N)\n
['Depth-First Search', 'Trie', 'C']