Problem

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

The special characters and their entities for HTML are:

  • Quotation Mark: the entity is " and symbol character is ".
  • Single Quote Mark: the entity is ' and symbol character is '.
  • Ampersand: the entity is & and symbol character is &.
  • Greater Than Sign: the entity is > and symbol character is >.
  • Less Than Sign: the entity is &lt; and symbol character is <.
  • Slash: the entity is &frasl; and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Examples

Example 1

1
2
3

Input: text = "&amp; is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the &amp; entity by &

Example 2

1
2

Input: text = "and I quote: &quot;...&quot;"
Output: "and I quote: \"...\""

Constraints

  • 1 <= text.length <= 10^5
  • The string may contain any possible characters out of all the 256 ASCII characters.

Solution

Method 1 – Hash Map Replacement

Intuition

We can use a hash map to store all HTML entities and their corresponding characters. Then, we scan the string and replace each entity with its character. This is efficient and easy to maintain.

Approach

  1. Create a hash map of all HTML entities and their replacements.
  2. Scan the input string and for each entity, replace it with its corresponding character.
  3. Return the modified string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string entityParser(string text) {
        vector<pair<string, string>> rep = {
            {"&quot;", "\""},
            {"&apos;", "'"},
            {"&amp;", "&"},
            {"&gt;", ">"},
            {"&lt;", "<"},
            {"&frasl;", "/"}
        };
        for (auto& [k, v] : rep) {
            size_t pos = 0;
            while ((pos = text.find(k, pos)) != string::npos) {
                text.replace(pos, k.size(), v);
                pos += v.size();
            }
        }
        return text;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func entityParser(text string) string {
    rep := []struct{ from, to string }{
        {"&quot;", `"`},
        {"&apos;", "'"},
        {"&amp;", "&"},
        {"&gt;", ">"},
        {"&lt;", "<"},
        {"&frasl;", "/"},
    }
    for _, r := range rep {
        text = strings.ReplaceAll(text, r.from, r.to)
    }
    return text
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public String entityParser(String text) {
        String[][] rep = {
            {"&quot;", "\""},
            {"&apos;", "'"},
            {"&amp;", "&"},
            {"&gt;", ">"},
            {"&lt;", "<"},
            {"&frasl;", "/"}
        };
        for (String[] r : rep) {
            text = text.replace(r[0], r[1]);
        }
        return text;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun entityParser(text: String): String {
        val rep = listOf(
            "&quot;" to '"',
            "&apos;" to '\'',
            "&amp;" to '&',
            "&gt;" to '>',
            "&lt;" to '<',
            "&frasl;" to '/'
        )
        var ans = text
        for ((k, v) in rep) ans = ans.replace(k, v.toString())
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def entityParser(self, text: str) -> str:
        rep = {
            '&quot;': '"',
            '&apos;': "'",
            '&amp;': '&',
            '&gt;': '>',
            '&lt;': '<',
            '&frasl;': '/',
        }
        for k, v in rep.items():
            text = text.replace(k, v)
        return text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn entity_parser(text: String) -> String {
        let mut t = text;
        let rep = [
            ("&quot;", "\""),
            ("&apos;", "'"),
            ("&amp;", "&"),
            ("&gt;", ">"),
            ("&lt;", "<"),
            ("&frasl;", "/"),
        ];
        for (k, v) in rep.iter() {
            t = t.replace(k, v);
        }
        t
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    entityParser(text: string): string {
        const rep: [string, string][] = [
            ['&quot;', '"'],
            ['&apos;', "'"],
            ['&amp;', '&'],
            ['&gt;', '>'],
            ['&lt;', '<'],
            ['&frasl;', '/'],
        ];
        for (const [k, v] of rep) text = text.split(k).join(v);
        return text;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m), where n is the length of the string and m is the number of entities (constant here).
  • 🧺 Space complexity: O(1), ignoring the output string, as replacements are done in place.