Scale Engineer

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 TableString

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

 

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 <= 105
  • 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.

import java.util.Map;import java.util.HashMap; class Solution {    public String entityParser(String text) {        Map<String, String> entityMap = new HashMap<>();        entityMap.put("&quot;", "\"");        entityMap.put("&apos;", "'");        entityMap.put("&amp;", "&");        entityMap.put("&gt;", ">");        entityMap.put("&lt;", "<");        entityMap.put("&frasl;", "/");         StringBuilder sb = new StringBuilder();        int i = 0;        int n = text.length();        while (i < n) {            if (text.charAt(i) == '&') {                int j = text.indexOf(';', i);                // Check if a semicolon exists and the substring is a valid entity                if (j != -1) {                    String entity = text.substring(i, j + 1);                    if (entityMap.containsKey(entity)) {                        sb.append(entityMap.get(entity));                        i = j + 1;                        continue;                    }                }            }            // If not an entity or not starting with '&', append the character            sb.append(text.charAt(i));            i++;        }        return sb.toString();    }}

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.

Solutions

class Solution {public  String entityParser(String text) {    Map<String, String> d = new HashMap<>();    d.put("&quot;", "\"");    d.put("&apos;", "'");    d.put("&amp;", "&");    d.put("&gt;", ">");    d.put("&lt;", "<");    d.put("&frasl;", "/");    StringBuilder ans = new StringBuilder();    int i = 0;    int n = text.length();    while (i < n) {      boolean found = false;      for (int l = 1; l < 8; ++l) {        int j = i + l;        if (j <= n) {          String t = text.substring(i, j);          if (d.containsKey(t)) {            ans.append(d.get(t));            i = j;            found = true;            break;          }        }      }      if (!found) {        ans.append(text.charAt(i++));      }    }    return ans.toString();  }}

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 →

Next problem