HTML Entity Parser

Medium

Google

4 views

Topics:

Strings

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: &quot;...&quot;"
Output: "and I quote: \"...\""

Constraints:

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

Try coding it in LeetCode

HTML Entity Parser

Medium

Google

4 views

Topics:

Strings

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: &quot;...&quot;"
Output: "and I quote: \"...\""

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters can appear in the input string besides HTML entities and standard text?
How should I handle nested or overlapping HTML entities (e.g., '&lt;')?
Is the input string guaranteed to be valid UTF-8, or do I need to handle potential encoding issues?
Are there any other HTML entities that I should handle besides the ones explicitly listed in the problem description (e.g., named character references)?
If an entity is malformed or unrecognized, should I leave it as is, remove it, or is there a specific error handling behavior?

Brute Force Solution

Approach

We're given some text that contains special codes representing characters, like '&' for '&'. The brute force method is to go through the text and check every possible code to see if it exists at each position. If we find a code, we replace it with the real character.

Here's how the algorithm would work step-by-step:

Look at the text from the very beginning, character by character.
At each character, check if the next few characters form any of the special codes we know (like '&', '<', '>', '"', ''').
If we find a matching code, replace the entire code sequence with the actual character it represents.
If we don't find a matching code, just leave the character as it is.
Move to the next character in the original text and repeat the process until we've looked at every character.

Code Implementation

def html_entity_parser(text):
    entity_map = {
        "&amp;": "&",
        "&lt;": "<",
        "&gt;": ">",
        "&quot;": '"',
        "&apos;": "'",
    }

    result = ""
    text_length = len(text)
    current_index = 0

    while current_index < text_length:
        found_entity = False

        # Iterate through known entities to replace
        for entity, character in entity_map.items():
            entity_length = len(entity)

            # Check if entity exists at current index
            if (
                current_index + entity_length <= text_length
                and text[current_index : current_index + entity_length] == entity
            ):

                # Replace the entity with the real character
                result += character
                current_index += entity_length
                found_entity = True

                break

        # If no entity found, append the current character
        if not found_entity:
            result += text[current_index]
            current_index += 1

    return result

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through the input string of length n. For each character in the string, it checks for the presence of a set of HTML entities. The maximum length of any HTML entity is k (e.g., '&' is 5, so k represents the length of the longest HTML entity that needs to be checked). In the worst case, at each character of the input string, we might need to compare a substring of length up to k with all known HTML entities. Therefore, the time complexity is O(n*k), where n is the length of the input string and k is the length of the longest HTML entity to be checked.

Space Complexity

O(N) – The algorithm iterates through the input text of length N and potentially replaces HTML entities. To handle these replacements, a new string (or character array) of size up to N may be created to store the parsed text. This new string consumes space proportional to the input size. Thus, the auxiliary space complexity is O(N), where N is the length of the input text.

Optimal Solution

Approach

We need to replace special HTML codes like '&' with their actual characters like '&'. The optimal way is to check the input string for known HTML codes and replace them as we find them. This approach avoids unnecessary work by directly addressing each code.

Here's how the algorithm would work step-by-step:

Look at the text character by character from start to finish.
If you find an '&', check if it's the start of a known HTML code.
To check, see if the characters after the '&' match any of the valid HTML codes like 'amp;', 'quot;', etc.
If it's a valid code, replace the whole code (like '&') with the correct character (like '&').
If it's not a valid code, leave the '&' as is and continue checking the rest of the text.
Keep doing this until you reach the end of the text, ensuring all valid codes are replaced correctly.

Code Implementation

def html_entity_parser(text):
    result = ''
    index = 0
    while index < len(text):
        if text[index] == '&':
            # Check for HTML entity codes
            if index + 4 < len(text) and text[index:index + 5] == '&amp;':
                result += '&'
                index += 5

            elif index + 5 < len(text) and text[index:index + 6] == '&quot;':
                result += '"'
                index += 6

            elif index + 5 < len(text) and text[index:index + 6] == '&apos;':
                result += ''
                index += 6

            elif index + 4 < len(text) and text[index:index + 5] == '&lt;':
                result += '<'
                index += 5

            elif index + 4 < len(text) and text[index:index + 5] == '&gt;':
                result += '>'
                index += 5

            elif index + 6 < len(text) and text[index:index + 7] == '&frasl;':
                result += '/'
                index += 7
            else:
                # If not a valid code, keep '&' as is
                result += '&'
                index += 1

        else:
            result += text[index]
            index += 1

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n character by character. Inside the loop, it checks for the presence of an '&' and, if found, compares the subsequent characters against a fixed set of HTML entity codes. The number of HTML entity codes to check is constant. Therefore, the time complexity is directly proportional to the length of the input string, resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the input string, character by character, and performs in-place replacements. It doesn't create any auxiliary data structures like lists, arrays, or hashmaps that scale with the input size N (where N is the length of the input string). The only extra memory used is for a few constant-size variables to keep track of the current position and potentially a temporary variable during replacement, independent of N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or handle as an error, depending on the requirements.
Input string contains only valid HTML entities.	The parser should correctly decode all entities without errors.
Input string contains no valid HTML entities.	The parser should return the original string unchanged.
Input string contains incomplete HTML entities (e.g., '&amp' without the ';')	Handle as an invalid entity and leave the incomplete sequence as is, or define a specific error handling mechanism.
Input string contains nested or overlapping potentially valid entities (e.g., '&ampamp;')	Define precedence rules and implement the resolution logic accordingly (e.g., treating it as '&amp' followed by 'amp;').
Input string contains multiple consecutive ampersands (e.g., '&&')	The parser should not get stuck and properly handle the sequence as ampersands followed by a valid or invalid entity.
Extremely long input strings to test scalability.	The algorithm needs to be efficient to avoid timeouts with large input sizes; use efficient string processing techniques.
Entities containing invalid or non-standard characters after the ampersand and before the semicolon.	Treat these as invalid entities and leave the characters unchanged in the output string.