Trie | C++ | Without Map
Inspired by  @votrubac\n\nclass Solution {\n  class Trie{\n      public:\n    Trie *children[26] = {};\n    char terminal = 0;\n\n    void insert(string &w, cha
### Inspired by  [@votrubac](https://leetcode.com/problems/html-entity-parser/discuss/575416/C%2B%2B-two-pointers-O(n)-or-O(1))\n```\nclass Solution {\n  class Trie{\n      public:\n    Trie *children[26] = {};\n    char terminal = 0;\n\n    void insert(string &w, char ch, int p = 0) {\n        if (p == w.size())\n            terminal = ch;\n        else {\n            if (children[w[p] - \'a\'] == nullptr)\n                children[w[p] - \'a\'] = new Trie();\n            children[w[p] - \'a\']->insert(w, ch, p + 1);\n        }\n    }\n\n    char isValid(string &word,int st,int sz){\n      if(terminal!=0 && sz==0){\n        return terminal;\n      }\n\n      if(word[st]<\'a\' || word[st]>\'z\' || children[word[st]-\'a\']==NULL){\n        return 0;\n      }\n\n      return children[word[st]-\'a\']->isValid(word,st+1,sz-1);\n    }\n  };\n\n\n  vector<pair<string, char>> special = {{"gt", \'>\'}, {"lt", \'<\'},\n    {"amp", \'&\'}, {"quot", \'"\'}, {"apos", \'\\\'\'}, {"frasl", \'/\'}};\n\n\npublic:\n  string entityParser(string s) {\n    Trie root;\n    //insert in trie\n    for(auto &[str,ch]:special){\n      root.insert(str,ch);\n    }\n\n    int st = 0,end = 0;\n    for(int i=0;i<s.size();i++,end++){\n      s[end] = s[i];\n      if(s[end]==\'&\'){\n        st = end;\n      }\n      if(s[end]==\';\'){\n        auto ch = root.isValid(s,st+1,end-st-1);\n        // if special char found then put that one\n        if(ch!=0){\n          end = st;\n          s[end] = ch;\n        }\n        //pointing to next char in string now\n        st = end+1;\n      }\n    }\n\n    s.resize(end);\n    return s;\n  }\n};\n```
['C']