Leetcode 1410: HTML Entity Parser
You are tasked with decoding a string that contains HTML entities. The HTML entities represent special characters like quotation marks, ampersands, greater-than signs, etc. You need to replace the HTML entities with their respective characters.
Problem
Approach
Steps
Complexity
Input: The input consists of a string with HTML entities.
Example: text = "The "HTML" language is popular."
Constraints:
• 1 <= text.length <= 105
• The string can contain any ASCII character.
Output: Return the decoded string where all the HTML entities are replaced by their corresponding characters.
Example: The output will be "The HTML language is popular."
Constraints:
Goal: Replace HTML entities in the string with their corresponding characters.
Steps:
• Initialize a map with HTML entity to character mappings.
• Iterate through the string, find any entity starting with '&' and ending with ';'.
• Check if the found entity exists in the map and replace it.
• Return the final decoded string.
Goal: Ensure the text length falls within the given constraints.
Steps:
• 1 <= text.length <= 105
• The string may contain any ASCII characters.
Assumptions:
• The input string contains valid HTML entities.
• Entities are well-formed and properly enclosed in '&' and ';'.
• Input: Input: text = "The "HTML" language is popular."
• Explanation: The parser will replace the entity " with " to produce the decoded string: "The HTML language is popular."
Approach: To solve this problem, we'll map the HTML entities to their corresponding characters and then iterate over the string to replace any encountered entities.
Observations:
• HTML entities are enclosed by '&' and ';'.
• Each entity corresponds to a special character.
• We can use a map to store the mappings and process the string character by character.
Steps:
• Create a map for the HTML entities.
• Iterate over the string and check for the presence of an entity.
• If an entity is found, replace it with its mapped character.
• Return the decoded string.
Empty Inputs:
• Handle an empty string input.
Large Inputs:
• Ensure that the solution handles strings near the upper constraint of length 105.
Special Values:
• Consider cases where there are no entities in the input.
Constraints:
• Ensure all HTML entities are valid and properly closed with ';'.
string entityParser(string text) {
map<string, string> mp;
mp["""] = "\"";
mp["'"] = "\'";
mp["&"] = "&";
mp[">"] = ">";
mp["<"] = "<";
mp["⁄"] = "/";
string res = "";
int i = 0;
while(i < text.size()) {
if(text[i] == '&') {
string tmp = "";
while(i < text.size() && text[i] != ';'){
tmp += text[i++];
if(i < text.size() && text[i] == '&') {
res += tmp;
tmp = "";
}
}
if(text[i] == ';') {
i++;
tmp += ';';
if(mp.count(tmp)) {
res += mp[tmp];
} else {
res += tmp;
}
} else {
res += tmp;
}
} else {
res += text[i++];
}
}
return res;
}
1 : String Manipulations
string entityParser(string text) {
This line defines the function `entityParser`, which takes a string `text` as input and returns a modified version of it.
2 : Variable Initialization
map<string, string> mp;
A map `mp` is initialized to store key-value pairs for replacing HTML entities with their corresponding characters.
3 : Map Operations
mp["""] = "\"";
Here, the `"` HTML entity is mapped to the double quote `"` character.
4 : Map Operations
mp["'"] = "\'";
The `'` entity is mapped to the single quote \'\' character.
5 : Map Operations
mp["&"] = "&";
The `&` entity is mapped to the `&` character.
6 : Map Operations
mp[">"] = ">";
The `>` entity is mapped to the greater-than `>` character.
7 : Map Operations
mp["<"] = "<";
The `<` entity is mapped to the less-than `<` character.
8 : Map Operations
mp["⁄"] = "/";
The `⁄` entity is mapped to the forward slash `/` character.
9 : Variable Initialization
string res = "";
The variable `res` is initialized as an empty string to accumulate the result.
10 : Variable Initialization
int i = 0;
The variable `i` is initialized to 0 and will be used as the index to iterate through the input string `text`.
11 : Loop Constructs
while(i < text.size()) {
A while loop is started to process each character in the input string `text`.
12 : Conditional Logic
if(text[i] == '&') {
Checks if the current character is the `&` symbol, which indicates the start of an HTML entity.
13 : Variable Initialization
string tmp = "";
A temporary string `tmp` is initialized to store potential HTML entities.
14 : Loop Constructs
while(i < text.size() && text[i] != ';'){
A nested while loop is used to collect characters until a semicolon `;` (end of the entity) is found.
15 : String Manipulations
tmp += text[i++];
Appends the current character to `tmp` and increments `i`.
16 : Conditional Logic
if(i < text.size() && text[i] == '&') {
Checks if another `&` is encountered within the entity, in which case the current entity is complete.
17 : String Manipulations
res += tmp;
Appends the current entity in `tmp` to the result string `res`.
18 : Variable Initialization
tmp = "";
Resets the temporary string `tmp` to collect a new entity.
19 : Conditional Logic
if(text[i] == ';') {
Checks if the current character is a semicolon, signaling the end of an HTML entity.
20 : Variable Initialization
i++;
Increments `i` to move past the semicolon.
21 : String Manipulations
tmp += ';';
Appends the semicolon to `tmp` to finalize the entity.
22 : Map Operations
if(mp.count(tmp)) {
Checks if the entity `tmp` exists in the `mp` map.
23 : String Manipulations
res += mp[tmp];
If the entity is found in the map, its corresponding character is appended to the result string.
24 : String Manipulations
} else {
Handles the case where the entity is not in the map.
25 : String Manipulations
res += tmp;
If the entity is not in the map, the raw entity is appended to the result string.
26 : Control Flow
} else {
If the character is not `&`, append it to the result string.
27 : String Manipulations
res += tmp;
Appends the accumulated characters in `tmp` to `res`.
28 : Loop Constructs
} else {
If the character is not `&`, it is directly appended to the result.
29 : String Manipulations
res += text[i++];
Appends the character to `res` and increments the index `i`.
30 : Return Statement
return res;
Returns the processed string `res`.
Best Case: O(n), where n is the length of the string.
Average Case: O(n), as we need to process each character in the string.
Worst Case: O(n), as we might encounter entities that require checking each character.
Description: The time complexity is linear in relation to the length of the string.
Best Case: O(n), as we need to store the result string.
Worst Case: O(n), where n is the length of the string.
Description: The space complexity is linear due to the additional space used to store the decoded string.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus