# HTML Entity Parser
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/html-entity-parser)
Canonical: https://scaleengineer.com/dsa/problems/html-entity-parser
**Data structures:** Hash Table, String
---
## 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 `<` and symbol character is `<`.
* **Slash:** the entity is `⁄` 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 = "& is an HTML entity but &ambassador; is not."
**Output:** "& is an HTML entity but &ambassador; is not."
**Explanation:** The parser will replace the & 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
## Brute Force using Chained replace()
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., `>`), it must be handled carefully. Replacing `&` with `&` first correctly transforms entities like `>` into `>`, which can then be processed by a subsequent `replace(">", ">")`. Therefore, the replacement for `&` should be performed first.
**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.
**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.
### Explanation
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 `&` is converted to `&`, other entities like `>` (which might have been `>` initially) can be correctly identified and replaced.
```java
class Solution {
public String entityParser(String text) {
// The order is important. & must be replaced first to handle cases like > which should become >.
// text.replace("&", "&") turns ">" into ">".
// Then text.replace(">", ">") correctly finishes the job.
return text.replace("&", "&")
.replace(""", "\"")
.replace("'", "'")
.replace(">", ">")
.replace("<", "<")
.replace("⁄", "/");
}
}
```
### Algorithm
- Start with the input string `text`.
- First, replace all occurrences of `&` with `&`. This is critical to do first so that compound entities like `>` 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 `⁄`.
- The final string after all replacements is the result.
## Optimized Single Pass with StringBuilder
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.
**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.
**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.
### Explanation
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.
```java
import java.util.Map;
import java.util.HashMap;
class Solution {
public String entityParser(String text) {
Map entityMap = new HashMap<>();
entityMap.put(""", "\"");
entityMap.put("'", "'");
entityMap.put("&", "&");
entityMap.put(">", ">");
entityMap.put("<", "<");
entityMap.put("⁄", "/");
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();
}
}
```
### 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.
# Solutions
### Java
```java
class Solution {
public
String entityParser(String text) {
Map d = new HashMap<>();
d.put(""", "\"");
d.put("'", "'");
d.put("&", "&");
d.put(">", ">");
d.put("<", "<");
d.put("⁄", "/");
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();
}
}
```
### CPP
```cpp
class Solution {
public:
string entityParser(string text) {
unordered_map d = {
{""", " \" "}, {"'", "'"}, {"&", "&"},
{">", ">"}, {"<", "<"}, {"⁄", "/"},
};
string ans = "";
int i = 0, n = text.size();
while (i < n) {
bool found = false;
for (int l = 1; l < 8; ++l) {
int j = i + l;
if (j <= n) {
string t = text.substr(i, l);
if (d.count(t)) {
ans += d[t];
i = j;
found = true;
break;
}
}
}
if (!found)
ans += text[i++];
}
return ans;
}
};
```
### Python
```python
class Solution:
def entityParser(self, text: str) -> str: d = {'"': '"', ''': "'", '&': "&", ">": '>', "<": '<', "⁄": '/', } 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)
```