[Java] Beat 100% Trie O(N)
Build a Trie for HTML entities.\nUse a StringBuilder to build the output string.\nTraverse the text and maintain a Trie node reference while traversing. (simila
Build a Trie for HTML entities.\nUse a StringBuilder to build the output string.\nTraverse the text and maintain a Trie node reference while traversing. (similar to [212. Word Search II](https://leetcode.com/problems/word-search-ii/))\nContinue to match each character and move the Trie node reference.\nIf matching a word in the Trie, then append the corresponding special string to the output StringBuilder.\nIf fail to match a word in the Trie in the halfway, just append the temporary string get during traversing each Trie node, and reset the Trie node reference.\nPlease check code comments for detail.\n\nTime Complexity: O(N)\nSpace Compelxity: O(N)\n\n```\nclass Solution {\n    private class Trie {\n        public boolean isEnd;\n        public char mappingSpecialChar;\n        public Map<Character, Trie> next = new HashMap<>();\n    }\n    public void addWord(Trie root, String w, char specialChar) {\n        Trie cur = root;\n        for (int i = 0; i < w.length(); i++) {\n            char c = w.charAt(i);\n            if (cur.next.containsKey(c)) {\n                cur = cur.next.get(c);\n            } else {\n                Trie next = new Trie();\n                cur.next.put(c, next);\n                cur = next;\n            }\n        }\n        cur.isEnd = true;\n        cur.mappingSpecialChar = specialChar;\n    }\n    public Trie buildTrie() {\n        Trie root = new Trie();     \n        addWord(root, "&quot;", \'"\');\n        addWord(root, "&apos;", \'\\\'\');\n        addWord(root, "&amp;", \'&\');\n        addWord(root, "&gt;", \'>\');\n        addWord(root, "&lt;", \'<\');\n        addWord(root, "&frasl;", \'/\');\n        return root;\n    }\n    public String entityParser(String text) {\n        Trie root = buildTrie();\n        StringBuilder tmp = new StringBuilder(); // temporary string holding characters get during traversing each Trie node\n        StringBuilder sb = new StringBuilder();\n        Trie cur = root; //trie node reference\n        for (int i = 0; i < text.length(); i++) {\n            char c = text.charAt(i);\n            if (cur.next.containsKey(c)) {\n                cur = cur.next.get(c);\n                tmp.append(c); // record each character during trie traversal\n                if (cur.isEnd) {\n                    // if matching a HTML entity in the trie, output the special string the entity mapped to\n                    sb.append(cur.mappingSpecialChar);\n                    cur = root; // reset the trie node reference\n                    tmp.setLength(0); // clear the temp string\n                }\n            } else {\n                if (tmp.length() != 0) {\n                    // if fail to match a word in trie during the half way of trie traversal\n\t\t\t\t\t// append the characters we get during traversing the trie\n                    sb.append(tmp).append(c);\n                    cur = root; // reset the trie node reference\n                    tmp.setLength(0); // clear the temp string\n                } else\n                    sb.append(c); // not doing any trie traversal. simply append the character.\n            }\n        }\n\t\treturn sb.toString();\n    }\n}\n```
[]