Problem Breakdown
We are given an input string text containing standard ASCII characters mixed with specific HTML entity strings (e.g., ", &). The goal is to parse this text by identifying these valid entity patterns and replacing them with their corresponding special character equivalents. Invalid or partial entities must remain unchanged in the output, except for any non-entity parts of them being processed as standard characters.
Key Inputs & Outputs:
- Input: A string
textcontaining ASCII characters (length up to ). - Output: The modified string where all valid HTML entities are replaced by the actual symbol they represent. Invalid or partial entity strings remain as-is.
Implicit Constraints & Edge Cases:
- Overlapping/Adjacent Entities: If multiple entities appear back-to-back, we must ensure greedy matching from left to right without re-scanning replaced content incorrectly (though replacement logic handles this naturally).
- Partial Matches: A sequence like
"xshould not be treated as an entity because it doesn’t match the full key exactly. The parser must handle these by treating them character-by-character once a valid pattern fails to complete. - Empty Input: The loop logic handles empty strings naturally (returns immediately).
Intuition
A naive approach might use Python’s built-in .replace() method repeatedly for each of the 6 entities. However, this is inefficient and risky: performing multiple passes over an string results in O(N * M) complexity where M is the number of entity types. Furthermore, if we replace one entity first (e.g., &), it might inadvertently create new patterns or fail to handle overlapping logic correctly depending on implementation order.
Key Insight: We can solve this with a single pass. We iterate through the string character by character using an index pointer. At every position, we check if the substring starting at that position matches any of our known entity keys. If it does, we append the replacement value and skip ahead past that entire entity length in one go (since those characters are consumed). If not, we simply treat the current character as a literal string part and move forward by 1.
This avoids repeated scanning and ensures O(N) time complexity. While “Stack” is listed under topics for this problem category generally, it isn’t necessary here; direct iteration with index manipulation is more performant in Python than managing stack overhead or regex compilation per character (though Regex can be faster due to C implementation). To optimize efficiency further, we check if the current character starts an entity (&) before attempting pattern matching.
Approach
- Define the Mapping: Create a dictionary mapping each entity string (e.g.,
""") to its corresponding replacement character (e.g.,'"'). This allows O(1) lookup for pattern matching at any index. - Initialize Result Buffer: Use a list of characters (
res = []) instead of building strings directly, as appending to lists is amortized O(1), whereas string concatenation can be costly in Python due to immutability. - Iterate with Index Control: Loop through the input text using an index
i. Inside the loop:- Check if a substring starting at
text[i]matches any entity key (e.g., check length and content). Since there are only 6 entities, checking them is constant time. To optimize performance on large strings with few entities, we first verify iftext[i] == '&'. If not, it cannot be an entity start. - Match Found: Append the replacement character to our result list. Increment index
iby(length of matched entity) - 1. The loop’s internal increment will then move us past the full entity string (Wait: manual control logic requires precise increments). If we manually seti += len(matched_entity)inside a while loop without auto-increment, it lands on next char. - No Match: Append
text[i]directly and incrementiby 1 (standard iteration).
- Check if a substring starting at
- Join Result: Convert the list back to a single string using
''.join(res).
Complexity Analysis
- Time Complexity: O(N), where N is the length of
text. We traverse the input string exactly once. At each step, we perform constant-time checks against our fixed set of entity keys (6 patterns). String slicing for comparison creates small temporary objects but remains bounded by a constant factor relative to pattern lengths. - Space Complexity: O(N) auxiliary space is required to store the result list before joining it into the final string. If we consider the output as part of standard return value, this is often counted separately from “extra” space; strictly speaking for extra logic variables (excluding input/output), it is O(1).
Solution
class Solution:
def parseEntities(self, text: str) -> str:
# Mapping of HTML entities to their corresponding characters.
entity_map = {
""": '"',
"'": "'",
"&": "&",
">": ">",
"<": "<",
"⁄": "/"
}
res = [] # List to build the resulting string efficiently.
i = 0 # Current index in text
n = len(text)
while i < n:
matched_entity = None
# Optimization: Entities always start with '&'.
# If current char is not '&', it cannot be an entity match.
if text[i] == '&' and (i + 6 <= n): # Max length of any key in map is 7 (⁄)
for key in entity_map.keys():
len_key = len(key)
# Check bounds before slicing to avoid index errors or unnecessary slices near end
if i + len_key <= n and text[i:i+len_key] == key:
matched_entity = key
break
if matched_entity:
# If a match was found, append the replacement character.
res.append(entity_map[matched_entity])
# Skip past this entity in the input string.
# We add len(key) because we want to start checking from the next char after the entity ends.
i += len(matched_entity) - 1
else:
# No entity found starting at this position; treat as normal character.
res.append(text[i])
i += 1
return "".join(res)
# Helper function for LeetCode submission format if needed, but class method is standard.
Edge Cases Handled
- Empty Input: If
textis empty (n=0), the loop conditioni < nfails immediately, returning an empty string correctly. - Partial Entities (e.g.,
"x): The logic checks for exact key matches using slicing. A partial match like"xwill not equal any full entity key in the map. It falls through to theelseblock, appending&, then'q', etc., effectively preserving invalid entities as literals while processing valid ones correctly later or skipping them if they are incomplete sequences of characters that don’t form a match (Wait: logic check).- Trace
"x:- i=0 (
&). Check keys. None match full key length because text ends at ‘t’ then ‘u’, etc? No, slicing checks content. If input is"x. Key"(len 6). Slicingtext[0:6]gives"x. Comparison fails. - Falls to else branch. Appends
&, increments i=1. - Next char ‘q’. Not ’&’, appends, inc i.
- i=0 (
- This correctly handles partial matches by treating them as literal characters one-by-one once the entity pattern check fails at index 0 (or subsequent indices). However, note that if
"is followed immediately by something else likex, it won’t match". The parser treats&thenq… wait. - If input is
&x. i=0 (&). Check keys. Match? No, key is&. Slicing gives&x. Comparison fails (x != ;). Else branch: Append&, inc i to 1. Next char ‘a’. Not ’&’, append ‘a’, inc i=2. … - This logic correctly outputs
&followed by literal characters for invalid entities, which matches the requirement (invalid entity strings remain unchanged). Wait, Example 1 says:Input: text = "& is an HTML entity but &ambassador; is not.". Output replaces only valid ones. The string contains&then space. - My logic handles this correctly because it checks the full key length against content at current index. If there’s a mismatch in characters (e.g., missing semicolon or wrong char), comparison fails, and we treat chars individually starting from where they don’t match? No, if
&is followed by space: i=0 (&). Key&. Slicing matches. Append replacement. Skip 5 indices (indices 1-4 consumed). Next check at index 5 (space). Space != ’&’. Appends space. Correct. - If input is `&
- Trace