An inverted index is the core data structure behind search engines. Instead of mapping documents to their words, it maps each word to the list of documents that contain it — enabling fast keyword lookups across a large corpus.
You are given a pre-built inverted index mappings, a dictionary where each key is a lowercase word and each value is a list of URLs (strings) that contain that word.
Given a query string containing one or more lowercase words separated by spaces, return the sorted list of URLs that contain all words in the query (i.e. the intersection of each word's postings list).
If any word in the query does not appear in the index, return an empty list. If mappings is None or empty, return an empty list.
Example 1:
Input: mappings = {"what": ["website1.com", "website2.com", "website4.com", "website7.com"], "is": ["website1.com", "website2.com", "website3.com", "website4.com"], "google": ["website1.com", "website2.com", "website4.com", "website7.com", "website8.com"]}, query = "what is google"
Output: ["website1.com", "website2.com", "website4.com"]
Explanation: Three URLs appear in all three postings lists.
Example 2:
Input: mappings = {"python": ["site_b.com", "site_a.com", "site_c.com"]}, query = "python"
Output: ["site_a.com", "site_b.com", "site_c.com"]
Explanation: Single-word query — return all URLs for "python", sorted lexicographically.
Example 3:
Input: mappings = {"cat": ["site1.com", "site2.com"], "dog": ["site3.com", "site4.com"]}, query = "cat dog"
Output: []
Explanation: No URL appears in both postings lists.
Constraints:
query is a non-empty string of lowercase words separated by single spacesmappings are lowercasemappings contain no duplicates0 <= len(mappings) <= 10^4