Practice/Google/Leetcode 1807. Evaluate the Bracket Pairs of a String

Leetcode 1807. Evaluate the Bracket Pairs of a String

CodingMust

Problem

You are given a template string that contains placeholder keys enclosed in parentheses. You are also given a list of key-value pairs representing available knowledge. Your task is to process the template string and replace each placeholder with its corresponding value from the knowledge list. If a key is not found in the knowledge list, replace it with a question mark ("?").

A placeholder is defined as a sequence of characters enclosed in parentheses, like "(key)". The keys inside parentheses do not contain nested parentheses, spaces, or special characters—they are simple alphanumeric identifiers.

Requirements

1. Build an efficient lookup structure from the knowledge list to enable fast key retrieval
2. Process the template string in a single pass to identify and replace placeholders
3. Replace each "(key)" with its corresponding value if the key exists in the knowledge list
4. Replace each "(key)" with "?" if the key does not exist in the knowledge list
5. Return the fully processed string with all replacements made

Constraints

• 1 <= s.length <= 100,000
• 0 <= knowledge.length <= 1,000
• 1 <= key.length, value.length <= 100
• All keys in the knowledge list are unique
• Placeholders in the string are non-nested
• The string may contain any printable ASCII characters
• Time complexity should be O(n + m) where n is the length of the string and m is the size of the knowledge list
• Space complexity should be O(m) for storing the knowledge mapping

Examples

Example 1:

Input: s = "(name) loves (sport)", knowledge = [["name", "Bob"], ["sport", "soccer"]] Output: "Bob loves soccer" Explanation: Both placeholders are found in the knowledge list and replaced with their values.

Example 2:

Input: s = "(language) is (adjective)", knowledge = [["language", "Python"]] Output: "Python is ?" Explanation: "language" is replaced with "Python", but "adjective" is not in the knowledge list, so it becomes "?".

Example 3:

Input: s = "No placeholders here", knowledge = [["key", "value"]] Output: "No placeholders here" Explanation: The string has no placeholders, so it remains unchanged.

Example 4:

Input: s = "(a)(b)(c)", knowledge = [["a", "1"], ["b", "2"], ["c", "3"]] Output: "123" Explanation: Three consecutive placeholders are replaced with their values.