A travel site wants to tag places, amenities and so on inside guest reviews. You get the review text and a list of known phrases, each with a category, and must wrap every mention of a known phrase as [category]{text}.
Implement:
def highlight(review: str, mapping: list[list[str]]) -> str
mapping is a list of [phrase, category] pairs. Rules:
- Case-insensitive match, original text kept. A phrase matches when the review's characters equal the phrase's, ignoring upper/lower case (ASCII). The output keeps the review's own spelling inside the braces.
- Whole words only. The character just before a match and the character just after it must each be either the edge of the review or a non-alphanumeric character (anything but
a-z,A-Z,0-9). So"gate"matches in"gate,"and"(gate)"but not in"gateway"or"tollgate". - Exact inner text. Phrases can have several words and punctuation. Everything between the first and last character must match exactly (apart from case), including spaces:
"golden gate"doesn't match"golden gate"with two spaces. - Left to right, longest first, no overlaps. Scan the review from the left. At each position where a match can start, use the longest phrase that matches there under rules 1-3, output it wrapped, and continue right after it. Text inside a replaced match is never matched again.
- If two entries have the same phrase (ignoring case), the one listed first wins.
Every phrase is non-empty and starts and ends with an alphanumeric character. Categories are arbitrary non-empty strings. Everything that isn't matched is copied unchanged.
review = "Golden Gate views! We walked the golden gate bridge, then ate at a gateway cafe."
mapping = [["golden gate", "landmark"], ["golden gate bridge", "bridge"],
["gate", "misc"], ["cafe", "food"]]
highlight(review, mapping)
# "[landmark]{Golden Gate} views! We walked the [bridge]{golden gate bridge}, then ate at a gateway [food]{cafe}."
highlight("big apple pies", [["big apple pie", "dessert"], ["big apple", "city"]])
# "[city]{big apple} pies" the longer phrase fails the whole-word rule, so the shorter one is used
Constraints: review up to 200,000 characters, up to 5,000 phrases of up to 50 characters. Trying every phrase at every position is far too slow.
Show hint
Put the lower-cased phrases in a trie and walk it from each position where a word starts.