HTML Entity Parser

Med

#1305Time: O(N), where N is the length of the string. We iterate through the string once. Inside the loop, `indexOf` and `substring` operations take time proportional to the length of the entity, which is a small constant. Map lookups are also constant on average. Thus, the overall complexity is linear.Space: O(N) in the worst case for the `StringBuilder`. The map uses constant extra space, as the number of entities is fixed.

Data structures

Hash Table String

Prompt

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 < 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.

Example 1:

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:

Input: text = "and I quote: "...""
Output: "and I quote: \"...\""

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

A more efficient approach is to parse the string in a single pass. We can iterate through the string, character by character, and build the result using a StringBuilder. When we encounter an ampersand &, we look ahead for a matching semicolon ;. If the substring between them corresponds to a known HTML entity, we append the special character; otherwise, we append the characters as they are. This avoids creating multiple intermediate strings.

Algorithm

Pre-populate a Map with the given HTML entity strings as keys and their corresponding special characters as values. This provides O(1) average time complexity for lookups.
Initialize a StringBuilder to efficiently build the result string.
Iterate through the input text using an index i.
At each character, check if it is an ampersand '&'.
If it is an '&', find the index j of the next semicolon ';'.
If a semicolon is found, extract the substring from i to j (inclusive).
Check if this substring exists as a key in our entity map.
- If it exists, append the mapped character to the StringBuilder and update the index i to j+1 to skip the processed entity.
- If it does not exist (e.g., &ambassador;), it's not a valid entity we need to parse. In this case, we treat the initial '&' as a literal character, append it to the StringBuilder, and increment i by 1.
If the character is not an '&', or if it was an '&' but did not form a valid entity, append the current character to the StringBuilder and increment i by 1.
After iterating through the entire string, convert the StringBuilder to a string and return it.

Walkthrough

This optimized approach processes the string from left to right, making decisions locally without needing to re-scan the entire string. A StringBuilder is used for efficient string construction, and a HashMap provides fast lookups for entities. When an '&' is found, we check for a potential entity ending with ';'. If a valid, recognized entity is found, it's replaced. Otherwise, the characters are appended literally. This ensures that each character of the input string is processed only once.

1import java.util.Map;2import java.util.HashMap;3 4class Solution {5    public String entityParser(String text) {6        Map<String, String> entityMap = new HashMap<>();7        entityMap.put("&quot;", "\"");8        entityMap.put("&apos;", "'");9        entityMap.put("&amp;", "&");10        entityMap.put("&gt;", ">");11        entityMap.put("&lt;", "<");12        entityMap.put("&frasl;", "/");13 14        StringBuilder sb = new StringBuilder();15        int i = 0;16        int n = text.length();17        while (i < n) {18            if (text.charAt(i) == '&') {19                int j = text.indexOf(';', i);20                // Check if a semicolon exists and the substring is a valid entity21                if (j != -1) {22                    String entity = text.substring(i, j + 1);23                    if (entityMap.containsKey(entity)) {24                        sb.append(entityMap.get(entity));25                        i = j + 1;26                        continue;27                    }28                }29            }30            // If not an entity or not starting with '&', append the character31            sb.append(text.charAt(i));32            i++;33        }34        return sb.toString();35    }36}

Complexity

Time

O(N), where N is the length of the string. We iterate through the string once. Inside the loop, `indexOf` and `substring` operations take time proportional to the length of the entity, which is a small constant. Map lookups are also constant on average. Thus, the overall complexity is linear.

Space

O(N) in the worst case for the `StringBuilder`. The map uses constant extra space, as the number of entities is fixed.

Trade-offs

Pros

More efficient than the chained replace() approach as it processes the string in a single pass.
Avoids the overhead of creating multiple intermediate strings, saving memory and reducing garbage collection pressure.

Cons

The code is slightly more complex to write and read compared to the chained replace() method.

A straightforward approach is to use the built-in String.replace() method. We can chain these calls to replace each HTML entity one by one. A crucial detail is the order of replacement. Since & is a component of other entities (e.g., &gt;), it must be handled carefully. Replacing & with & first correctly transforms entities like &gt; into >, which can then be processed by a subsequent replace(">", ">"). Therefore, the replacement for & should be performed first.

Algorithm

Start with the input string text.
First, replace all occurrences of & with &. This is critical to do first so that compound entities like &gt; are correctly transformed into > before the next replacement step.
Then, replace all occurrences of " with ".
Continue this process for all other specified HTML entities: ', >, <, and &frasl;.
The final string after all replacements is the result.

Walkthrough

This method leverages the simplicity of Java's built-in string manipulation functions. By calling replace() for each entity in a specific order, we can solve the problem concisely. The key is to replace & first, as it can be a prefix for other entities. Once &amp; is converted to &, other entities like > (which might have been &gt; initially) can be correctly identified and replaced.

1class Solution {2    public String entityParser(String text) {3        // The order is important. &amp; must be replaced first to handle cases like &amp;gt; which should become >.4        // text.replace("&amp;", "&") turns "&amp;gt;" into "&gt;".5        // Then text.replace("&gt;", ">") correctly finishes the job.6        return text.replace("&amp;", "&")7                   .replace("&quot;", "\"")8                   .replace("&apos;", "'")9                   .replace("&gt;", ">")10                   .replace("&lt;", "<")11                   .replace("&frasl;", "/");12    }13}

Complexity

Time

O(N), where N is the length of the input string. Each `replace()` call scans the string and builds a new one, taking O(N) time. Since we perform a constant number of replacements (6), the total time complexity is linear, though with a higher constant factor than a single-pass solution.

Space

O(N), where N is the length of the input string. Each `replace()` call potentially creates a new string of length similar to the input string. This results in intermediate string allocations, leading to linear space complexity.

Trade-offs

Pros

Extremely simple and concise to implement.
Easy to read and understand.

Cons

Inefficient due to the creation of multiple intermediate strings, which can lead to higher memory usage and garbage collection overhead, especially for very long input strings.
The constant factor for time complexity is higher than a single-pass approach.

Solutions

Solution

1class Solution {2public3  String entityParser(String text) {4    Map<String, String> d = new HashMap<>();5    d.put("&quot;", "\"");6    d.put("&apos;", "'");7    d.put("&amp;", "&");8    d.put("&gt;", ">");9    d.put("&lt;", "<");10    d.put("&frasl;", "/");11    StringBuilder ans = new StringBuilder();12    int i = 0;13    int n = text.length();14    while (i < n) {15      boolean found = false;16      for (int l = 1; l < 8; ++l) {17        int j = i + l;18        if (j <= n) {19          String t = text.substring(i, j);20          if (d.containsKey(t)) {21            ans.append(d.get(t));22            i = j;23            found = true;24            break;25          }26        }27      }28      if (!found) {29        ans.append(text.charAt(i++));30      }31    }32    return ans.toString();33  }34}

1class Solution {2public:3  string entityParser(string text) {4    unordered_map<string, string> d = {5        {"&quot;", " \" "}, {"&apos;", "'"}, {"&amp;", "&"},6        {"&gt;", ">"},      {"&lt;", "<"},   {"&frasl;", "/"},7    };8    string ans = "";9    int i = 0, n = text.size();10    while (i < n) {11      bool found = false;12      for (int l = 1; l < 8; ++l) {13        int j = i + l;14        if (j <= n) {15          string t = text.substr(i, l);16          if (d.count(t)) {17            ans += d[t];18            i = j;19            found = true;20            break;21          }22        }23      }24      if (!found)25        ans += text[i++];26    }27    return ans;28  }29};

1class Solution:2    def entityParser(self, text: str) -> str: d = {'&quot;': '"', '&apos;': "'", '&amp;': "&", "&gt;": '>', "&lt;": '<', "&frasl;": '/', } i, n = 0, len(text) ans = [] while i < n: for l in range(1, 8): j = i + l if text[i: j] in d: ans . append(d[text[i: j]]) i = j break else: ans . append(text[i]) i += 1 return '' . join(ans)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem