HTML Entity Parser solution and explanation
Google
5 more videos on this problem
Leetcode 1410. HTML Entity ParserFraz · 5:50 · 932 views
HTML Entity Parser (Leetcode 1410)Coding Interviews · 12:44 · 497 views
1410. HTML Entity Parser | LeetCode | Linear time complexity | JAVAHarjinder Saggu · 5:56 · 439 views
1410. HTML Entity ParserMuerde un zombie · 8:00 · 98 views
小飞羊 LeetCode 1410. HTML Entity Parser - 套路得人薪C++Willy小飞羊 DJ · 4:54 · 42 views
LeetCode 1410: HTML Entity ParserAlitaCode · 23:12 · 5 views
The 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.
Approach overview
Problem Overview: You receive a string containing HTML entities such as &, <, or >. The task is to replace these encoded entities with their corresponding characters while leaving all other text unchanged.
Approach 1: Using Map for Entity Replacement (O(n) time, O(1) space)
This approach scans the string from left to right and replaces known HTML entities using a lookup table. Store all valid entities in a hash map where the key is the encoded entity (for example &) and the value is the decoded character (&). When you encounter the character '&', start checking substrings up to the next ';'. If the substring matches a key in the map, append the mapped character to the result and skip the processed characters. Otherwise, treat it as normal text. Because each character is processed at most once, the total time complexity is O(n). The map contains a constant number of entities, so the extra space is O(1). This method relies heavily on fast hash lookups, making it a practical use of a hash table combined with efficient string traversal.
The key insight is recognizing that the number of valid HTML entities is fixed. Instead of complex parsing logic, you simply check whether the substring matches one of the allowed tokens. This keeps the implementation straightforward and avoids unnecessary backtracking.
Approach 2: Regular Expression Replacement (O(n) time, O(1) space)
Another clean solution uses a regular expression to match any valid entity pattern and replace it through a callback or replacement function. Define a regex pattern that matches the allowed entities such as &(quot|apos|amp|gt|lt|frasl);. During replacement, map the captured entity name to its decoded character. Most modern regex engines process this in linear time relative to the string length, giving an effective O(n) time complexity with O(1) auxiliary space aside from the output string.
This approach reduces manual parsing logic and keeps the code concise. It works especially well in languages with strong regex support such as JavaScript or C#. Conceptually, the regex acts as a filter that only targets valid entity tokens, leaving all other characters untouched.
Recommended for interviews: The hash map scanning approach is typically preferred. It demonstrates clear control over string parsing, efficient use of a hash table, and predictable linear complexity. Interviewers often expect candidates to show how they detect an entity starting at '&', check the substring, and append the correct character. Regex solutions are valid but may hide the algorithmic reasoning behind library abstractions.
Approach 1: Using Map for Entity Replacement
In this approach, we create a mapping dictionary for all the known HTML entities and their corresponding special characters. As we traverse the input text, we check for any substrings starting with '&' that match an entity in our dictionary. If a match is found, we replace it with its corresponding character. This approach efficiently handles replacements using a single pass through the text.
def entityParser(text):
entities = {
'"': '"',
''': "'",
'&': '&',
'>': '>',
'<': '<',
'⁄': '/'
}
i, n = 0, len(text)
result = []
while i < n:
if text[i] == '&':
for entity in entities:
if text.startswith(entity, i):
result.append(entities[entity])
i += len(entity)
break
else:
# if no entity matches, append the '&' itself
result.append(text[i])
i += 1
else:
result.append(text[i])
i += 1
return ''.join(result)public class EntityParser {
public String entityParser(String text) {
Map<String, String> entityMap = Map.of(
""", "\"",
"'", "'",
"&", "&",
">", ">",
"<", "<",
"⁄", "/"
);
StringBuilder result = new StringBuilder();
int i = 0;
while (i < text.length()) {
if (text.charAt(i) == '&') {
boolean matchFound = false;
for (String entity : entityMap.keySet()) {
if (text.startsWith(entity, i)) {
result.append(entityMap.get(entity));
i += entity.length();
matchFound = true;
break;
}
}
if (!matchFound) {
result.append(text.charAt(i));
i++;
}
} else {
result.append(text.charAt(i));
i++;
}
}
return result.toString();
}
}The function entityParser initializes a dictionary with known HTML entities. It then iterates over the input string, checking for entities starting with &. If an entity from the dictionary is found, it appends the corresponding character to the result list and skips to the next unmatched character. It appends characters that do not start entities directly to the result list.
Time Complexity: O(n * m), where n is the length of the input text and m is the average length of the entities. Since there are a fixed number of entities, this effectively reduces to O(n).
Space Complexity: O(n), for storing the output result.
Approach 2: Regular Expression Replacement
This approach utilizes regular expressions to simplify the replacement of HTML entities. By compiling regular expressions for each entity, we can quickly substitute occurrences within the string.
function entityParser(text) {
const entities = {
'"': '"',
''': "'",
'&': '&',
'>': '>',
'<': '<',
'⁄': '/'
};
for (const [entity, character] of Object.entries(entities)) {
const regex = new RegExp(entity, 'g');
text = text.replace(regex, character);
}
return text;
}using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
public class HtmlEntityParser
{
public string EntityParser(string text)
{
Dictionary<string, string> entities = new Dictionary<string, string>
{
{ """, "\"" },
{ "'", "'" },
{ "&", "&" },
{ ">", ">" },
{ "<", "<" },
{ "⁄", "/" }
};
foreach (var kvp in entities)
{
text = Regex.Replace(text, Regex.Escape(kvp.Key), kvp.Value);
}
return text;
}
}The entityParser function uses a dictionary to store the HTML entities. For each entity-character pair, it constructs a regex and replaces all occurrences of the entity in the text with the character.
Time Complexity: O(n * m), where n is the length of text and m is the number of entities. Each entity replacement triggers a separate regex operation.
Space Complexity: O(n), considering the space needed for the resultant string.
Approach 3: Hash Table + Simulation
We can use a hash table to store the corresponding character for each character entity. Then, we traverse the string, and when we encounter a character entity, we replace it with the corresponding character.
The time complexity is O(n times l), and the space complexity is O(l). Here, n is the length of the string, and l is the total length of the character entities.
class Solution {
public:
string entityParser(string text) {
unordered_map<string, string> 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;
}
};function entityParser(text: string): string {
const d: Record<string, string> = {
'"': '"',
''': "'",
'&': '&',
'>': '>',
'<': '<',
'⁄': '/',
};
let ans: string = '';
let i: number = 0;
const n: number = text.length;
while (i < n) {
let found: boolean = false;
for (let l: number = 1; l < 8; ++l) {
const j: number = i + l;
if (j <= n) {
const t: string = text.substring(i, j);
if (d.hasOwnProperty(t)) {
ans += d[t];
i = j;
found = true;
break;
}
}
}
if (!found) {
ans += text[i++];
}
}
return ans;
}func entityParser(text string) string {
d := map[string]string{
""": "\"",
"'": "'",
"&": "&",
">": ">",
"<": "<",
"⁄": "/",
}
var ans strings.Builder
i, n := 0, len(text)
for i < n {
found := false
for l := 1; l < 8; l++ {
j := i + l
if j <= n {
t := text[i:j]
if val, ok := d[t]; ok {
ans.WriteString(val)
i = j
found = true
break
}
}
}
if !found {
ans.WriteByte(text[i])
i++
}
}
return ans.String()
}Approach 4: Default Approach
function entityParser(text: string): string {
const d: { [key: string]: string } = {
'"': '"',
''': "'",
'&': '&',
'>': '>',
'<': '<',
'⁄': '/',
};
const pattern = new RegExp(Object.keys(d).join('|'), 'g');
return text.replace(pattern, match => d[match]);
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Map for Entity Replacement | Time Complexity: O(n * m), where n is the length of the input text and m is the average length of the entities. Since there are a fixed number of entities, this effectively reduces to O(n). |
| Regular Expression Replacement | Time Complexity: O(n * m), where n is the length of text and m is the number of entities. Each entity replacement triggers a separate regex operation. |
| Hash Table + Simulation | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Map-Based Entity Replacement | O(n) | O(1) | Best general solution for interviews and clear algorithmic control over parsing |
| Regular Expression Replacement | O(n) | O(1) | Useful when the language has strong regex support and you want concise code |
Frequently asked questions
Is HTML Entity Parser easy or hard?
HTML Entity Parser is generally rated Medium difficulty. The main challenge is correctly identifying entity boundaries and replacing them without misinterpreting normal text. Once the entity mapping is defined, the implementation becomes a straightforward linear scan.
HTML Entity Parser Python/Java solution
In Python or Java, the typical solution defines a dictionary or HashMap containing mappings such as "&" to "&" and "<" to "<". Iterate through the string and check substrings whenever '&' appears. Replace recognized entities and append characters to a result builder.
How to solve HTML Entity Parser in O(n)?
Traverse the string and detect potential entities whenever you see '&'. Extract the substring up to the next ';' and check it against a predefined hash map of valid entities like &, <, and >. If a match exists, append the mapped character; otherwise keep the original text. Each character is visited once, resulting in linear time.
What is the best approach for HTML Entity Parser?
The hash map scanning approach is the most practical solution. Store all valid HTML entities in a map and iterate through the string, checking substrings that start with '&'. Each lookup takes constant time, giving an overall time complexity of O(n) with O(1) extra space.
Is HTML Entity Parser asked at Google/Amazon/Meta?
Problems involving string parsing and token replacement frequently appear in interviews at companies like Google, Amazon, and Meta. HTML Entity Parser specifically tests careful string traversal, pattern recognition, and efficient use of hash tables.
What data structure is used in HTML Entity Parser?
The most common data structure is a hash table that maps encoded entities to their decoded characters. This allows constant-time lookup when an entity substring is detected. The algorithm also relies on sequential string traversal.
What is the time complexity of HTML Entity Parser?
The optimal solution runs in O(n) time where n is the length of the input string. Each character is processed once, and entity detection uses constant-time hash lookups. Space complexity is O(1) because the entity mapping contains a fixed number of entries.