<p><strong>HTML entity parser</strong> is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.</p>

<p>The special characters and their entities for HTML are:</p>

<ul>
	<li><strong>Quotation Mark:</strong> the entity is <code>&amp;quot;</code> and symbol character is <code>&quot;</code>.</li>
	<li><strong>Single Quote Mark:</strong> the entity is <code>&amp;apos;</code> and symbol character is <code>&#39;</code>.</li>
	<li><strong>Ampersand:</strong> the entity is <code>&amp;amp;</code> and symbol character is <code>&amp;</code>.</li>
	<li><strong>Greater Than Sign:</strong> the entity is <code>&amp;gt;</code> and symbol character is <code>&gt;</code>.</li>
	<li><strong>Less Than Sign:</strong> the entity is <code>&amp;lt;</code> and symbol character is <code>&lt;</code>.</li>
	<li><strong>Slash:</strong> the entity is <code>&amp;frasl;</code> and symbol character is <code>/</code>.</li>
</ul>

<p>Given the input <code>text</code> string to the HTML parser, you have to implement the entity parser.</p>

<p>Return <em>the text after replacing the entities by the special characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;&amp;amp; is an HTML entity but &amp;ambassador; is not.&quot;
<strong>Output:</strong> &quot;&amp; is an HTML entity but &amp;ambassador; is not.&quot;
<strong>Explanation:</strong> The parser will replace the &amp;amp; entity by &amp;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;and I quote: &amp;quot;...&amp;quot;&quot;
<strong>Output:</strong> &quot;and I quote: \&quot;...\&quot;&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text.length &lt;= 10<sup>5</sup></code></li>
	<li>The string may contain any possible characters out of all the 256 ASCII characters.</li>
</ul>

class Node:
    def __init__(self):
        self.children = {}
        self.end_of_word = None

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word, replacement):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = Node()
            curr = curr.children[ch]
        curr.end_of_word = replacement

    def query(self, word, idx):
        curr = self.root
        while idx < len(word):
            ch = word[idx]
            if ch not in curr.children:
                return None, None
            
            curr = curr.children[ch]
            
            if curr.end_of_word is not None:
                return curr.end_of_word, idx

            idx += 1

        return None, None

class Solution:
    def entityParser(self, text: str) -> str:
        
        li = list(text)

        words = ["&quot;", "&apos;", "&amp;", "&gt;", "&lt;", "&frasl;"]
        replacements = ["\"", "\'", "&", ">", "<", "/"]

        trie = Trie()
        for word, rep in zip(words, replacements):
            trie.insert(word, rep)
        
        idx = 0
        while idx < len(li):
            rep, end_idx = trie.query(li, idx)
            if rep is None:
                idx += 1
                continue

            li[idx] = rep
            ch = li[idx]
            for nidx in range(idx + 1, end_idx + 1):
                li[nidx] = ""
            
            idx = end_idx + 1

        return "".join(li)
246