~/problems / Tries

Tag known phrases in a guest review

medium ~35 min Airbnb

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:

  1. 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.
  2. 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".
  3. 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.
  4. 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.
  5. 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.

Topic: Trie. Prefix tree; longest-match tokenizing.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc