You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.
"(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [keyi, valuei] indicates that key keyi has a value of valuei.
You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key keyi, you will:
keyi and the bracket pair with the key's corresponding valuei.keyi and the bracket pair with a question mark "?" (without the quotation marks).Each key will appear at most once in your knowledge. There will not be any nested brackets in s.
Return the resulting string after evaluating all of the bracket pairs.
Example 1:
Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]] Output: "bobistwoyearsold" Explanation: The key "name" has a value of "bob", so replace "(name)" with "bob". The key "age" has a value of "two", so replace "(age)" with "two".
Example 2:
Input: s = "hi(name)", knowledge = [["a","b"]] Output: "hi?" Explanation: As you do not know the value of the key "name", replace "(name)" with "?".
Example 3:
Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]] Output: "yesyesyesaaa" Explanation: The same key can appear multiple times. The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes". Notice that the "a"s not in a bracket pair are not evaluated.
Constraints:
1 <= s.length <= 1050 <= knowledge.length <= 105knowledge[i].length == 21 <= keyi.length, valuei.length <= 10s consists of lowercase English letters and round brackets '(' and ')'.'(' in s will have a corresponding close bracket ')'.s will be non-empty.s.keyi and valuei consist of lowercase English letters.keyi in knowledge is unique.Problem Overview: You receive a string s containing keys wrapped in parentheses such as (name) and a knowledge base of key–value pairs. Every key inside brackets must be replaced with its mapped value. If a key does not exist in the knowledge base, replace it with "?". The challenge is scanning the string efficiently while resolving keys quickly.
Approach 1: Using Dictionary or Map for Fast Key Lookup (O(n) time, O(k) space)
Store all knowledge pairs in a hash map so each key lookup runs in constant time. Iterate through the string character by character. When you encounter '(', start collecting characters until the closing ')' to form the key. Perform a direct hash lookup in the map and append the mapped value (or "?" if the key does not exist) to the result string. Characters outside brackets are appended normally. This approach processes each character once, making the total runtime O(n) where n is the length of the string, while the map requires O(k) space for k knowledge entries. The method relies heavily on hash table lookups and efficient string traversal.
Approach 2: Using Regular Expressions and String Replacement (O(n + m) time, O(k) space)
Another option uses a regular expression to locate patterns like \((.*?)\). First store the knowledge pairs in a map for constant-time lookup. The regex engine scans the string to find every bracketed key. For each match, replace the captured key with its corresponding value from the map or "?" if missing. This approach is concise and works well in languages with strong regex support such as Java or C#. Runtime is roughly O(n + m), where n is the string length and m is the number of matches processed. Space usage remains O(k) for storing the mapping. While elegant, regex may introduce overhead compared with manual parsing.
Recommended for interviews: The dictionary + manual scan approach is what interviewers expect. It demonstrates strong control over string parsing and efficient use of a hash table. Regex solutions are shorter but hide the underlying logic and may not always be optimal in performance-critical situations. Showing the direct parsing approach proves you can manage edge cases, handle missing keys, and maintain linear time complexity.
This approach leverages a hashmap (or dictionary) to store the 'knowledge' key-value pairs for efficient lookup. The idea is to traverse the input string 's' character by character, recognizing and processing the sections enclosed in brackets, and replacing them with their corresponding values from the hashmap. If the key isn't found in the hashmap, replace it with a '?'.
The code first creates a dictionary from the 'knowledge' list for quick key look-ups. It then iterates over the string 's', identifying bracketed keys and replacing them based on the dictionary. If a key is not found, it substitutes it with '?'. The result list gathers the output string which is constructed using efficient concatenation.
Python
JavaScript
Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) for storing the dictionary.
This approach takes advantage of regular expressions to identify bracketed pairs and performed batch string replacements based on the knowledge. This is efficient for scenarios with multiple replacements.
In this solution, a HashMap is utilized to map knowledge keys to their values. The string is traversed, and when bracketed sections are encountered, they are processed and replaced in the output using the hashmap for swift retrieval, much like the first approach but detailed for Java syntax.
Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) due to storage of dictionary elements.
First, we use a hash table d to record the key-value pairs in knowledge.
Then we traverse the string s. If the current character is an open parenthesis '(', we start traversing from the current position until we encounter a close parenthesis ')'. At this point, the string within the parentheses is the key. We look for the corresponding value of this key in the hash table d. If found, we replace the value within the parentheses with it, otherwise, we replace it with '?'.
The time complexity is O(n + m), and the space complexity is O(L). Here, n and m are the lengths of the string s and the list knowledge respectively, and L is the sum of the lengths of all strings in knowledge.
| Approach | Complexity |
|---|---|
| Approach 1: Using Dictionary or Map for Fast Key Lookup | Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) for storing the dictionary. |
| Approach 2: Using Regular Expressions and String Replacement | Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) due to storage of dictionary elements. |
| Hash Table + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dictionary / Map with Manual String Parsing | O(n) | O(k) | Best general solution. Linear scan with constant-time key lookup. |
| Regular Expression Replacement | O(n + m) | O(k) | Useful when regex libraries are strong and concise code is preferred. |
LeetCode 1807. Evaluate the Bracket Pairs of a String | Visualization | Python • AH Tech • 402 views views
Watch 9 more video solutions →Practice Evaluate the Bracket Pairs of a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor