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.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.
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.
C#
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.
| 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. |
Valid Parentheses - Stack - Leetcode 20 - Python • NeetCode • 475,216 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