Complex String Manipulation

HardPython

Problem

Nextdoor search supports simple query expressions over post text. Implement a function that determines whether a post matches a query containing ordinary terms, quoted phrases, and exclusions.

A positive term or phrase must appear in the post. All positive clauses must match. A clause prefixed with - must not appear. Matching is case-insensitive, and punctuation separates words. Terms match whole words, while quoted phrases must match consecutive whole words.

Formal Specification

Implement matches_post(post, query), where both arguments are strings. Return True if the post satisfies every clause in the query, otherwise return False.

The query is valid and follows these rules:

Terms are separated by one or more spaces.
A phrase is enclosed in double quotes, such as "street parking".
A negative clause starts with -, such as -sale or -"garage sale".
Punctuation inside a term or phrase is treated as a word separator.
An empty query matches every post.

Constraints

0 <= len(post), len(query) <= 100,000
The query contains at most 100 clauses
A quoted phrase contains at most 20 words
Query syntax is valid and all quoted phrases are closed
Matching is case-insensitive

Function Signature

def matches_post(post, query):

Nextdoor search supports simple query expressions over post text. Implement a function that determines whether a post matches a query containing ordinary terms, quoted phrases, and exclusions.

Formal Specification

Implement matches_post(post, query), where both arguments are strings. Return True if the post satisfies every clause in the query, otherwise return False.

The query is valid and follows these rules:

Terms are separated by one or more spaces.
A phrase is enclosed in double quotes, such as "street parking".
A negative clause starts with -, such as -sale or -"garage sale".
Punctuation inside a term or phrase is treated as a word separator.
An empty query matches every post.