Trie Best Approach in Linear Time | Easy C++ Solution
Approach\n Describe your approach to solving the problem. \n1. Node class: Represents a node in the Trie. It contains an array of pointers links representing ch
# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Node class: Represents a node in the Trie. It contains an array of pointers links representing child nodes for each character from \'a\' to \'z\'. It also has a boolean flag flag indicating whether the node marks the end of a word.\ncontainsKey(char ch): Checks if the current node contains a child node for the given character.\nadd(char ch, Node* node): Adds a child node for the given character.\nget(char ch): Retrieves the child node for the given character.\nsetEnd(): Marks the current node as the end of a word.\nisEnd(): Checks if the current node marks the end of a word.\n2. Trie class: Implements the Trie data structure.\ninsert(string str): Inserts a word into the Trie by iterating over each character in the word and creating nodes if necessary.\nisAns(string str): Checks if the given string exists in the Trie by traversing the Trie and ensuring each character is part of a valid word.\n\n# Complexity\n- Time complexity: O(n * L), where n is the number of words and L is the average length of the words.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n * L), where n is the number of words and L is the average length of the words.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Node{\nprivate:\n    Node*links[26];\n    bool flag=false;\n\npublic:\n    bool containsKey(char ch){\n        return links[ch-\'a\']!=NULL;\n    }\n    void add(char ch,Node*node){\n        links[ch-\'a\']=node;\n    }\n    Node* get(char ch){\n        return links[ch-\'a\'];\n    }\n    void setEnd(){\n        flag=true;\n    }\n    bool isEnd(){\n        return flag;\n    }\n};\nclass Trie{\npublic:\n    Node*root;\n    Trie(){\n        root=new Node();\n    }\n    void insert(string str){\n        Node*node=root;\n        for(auto it:str){\n            if(!node->containsKey(it))\n                node->add(it,new Node());\n            node=node->get(it);\n        }\n        node->setEnd();\n    }\n   bool isAns(string str) {\n    Node* node = root;\n    for(auto it : str) {\n        if(!node->containsKey(it) || !node->get(it)->isEnd())\n            return false;\n        node = node->get(it);\n    }\n    return true; \n}\n\n};\nclass Solution {\npublic:\n    string longestWord(vector<string>& words) {\n        Trie trie;\n        for(auto it:words)\n            trie.insert(it);\n        \n        string ans = "";\n        for(auto word: words) {\n            if(trie.isAns(word)) {\n                if(word.size() > ans.size()) {\n                    ans = word;\n                } else if(word.size() == ans.size()) {\n                    ans = min(ans, word);\n                }\n            }\n        }\n\n        return ans;\n    }\n};\n```
['C++']