Watch 10 video solutions for Evaluate the Bracket Pairs of a String, a medium level problem involving Array, Hash Table, String. This walkthrough by AH Tech has 402 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |