Evaluate the Bracket Pairs of a String Solution In C++/Java/Python/Javascript
Problem Description
You are given a strings that contains some bracket pairs, with each pair containing a non-empty key.
For example, in the string "(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] = [key i, value i] indicates that key key i has a value of value I.
You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key key i, you will:
Replace key i and the bracket pair with the key's corresponding value I.
If you do not know the value of the key, you will replace key i 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
Input 1: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output 1: "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".
Input 2: s = "hi(name)", knowledge = [["a","b"]]
Output 2: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".
Constraints
1 <= s.length <= 10^5
0 <= knowledge.length <= 10^5
knowledge[i].length == 2
1 <= key i.length, value i.length <= 10
s consists of lowercase English letters and round brackets '(' and ')'.
Every open bracket '(' in s will have a corresponding close bracket ')'.
The key in each bracket pair of s will be non-empty.
There will not be any nested bracket pairs in s.
key i and value i consist of lowercase English letters.
Each key i in knowledge is unique.
The problem requires identifying bracketed keys in a string and replacing them with their corresponding values from a given knowledge list. The most straightforward approach is to scan the string, extract each key inside brackets, and search for its value in the provided list. However, repeatedly scanning the list for each key would be inefficient. Instead, storing key-value pairs in a hash map allows for constant-time lookups, ensuring an optimal and scalable solution.
Brute Force Approach
Intuition
The brute force approach involves scanning the given string s multiple times to find and replace bracketed keys with their corresponding values. Since we do not store the key-value pairs efficiently, every time a key is encountered, we must manually search for it in the given list of key-value pairs.
Each time we find a bracketed key, we iterate through the list of key-value pairs to check if a matching key exists. If a match is found, we replace the key with its corresponding value. If no match is found, we replace the key with a question mark. This process is repeated for each bracketed key in the string, leading to unnecessary repeated lookups.
Since both the string and the list of key-value pairs can be large, this approach results in high computational cost. Given that the list of key-value pairs can contain up to 100,000 elements, and the string can also be of length 100,000, this results in an inefficient time complexity, making it impractical for large inputs.
Approach
Step 1: Iterate through the string and identify the positions of opening and closing brackets. Extract the key between them.
Step 2: Iterate through the list of key-value pairs to check if a matching key exists. If a match is found, replace the bracketed key with its corresponding value. If no match is found, replace it with a question mark.
Step 3: Construct the final result by appending each character of the string directly unless a bracketed key is found, in which case the replaced value is appended instead.
Step 4: Repeat this process until the entire string has been processed.
Since this approach performs a linear scan of the string while searching for each key in the list of key-value pairs, it leads to a time complexity of O(n × k), where n is the length of the string and k is the number of key-value pairs.
Dry Run
Input:
s = (name)is(age)yearsold
knowledge = [["name", "bob"], ["age", "two"]]
Output:
bobistwoyearsold
Step 1: Iterate through s to find bracketed keys
- Scanning through the string, we detect the first bracket pair:
- Encounter ( at index 0.
- Extract key name from s[1:5], fetching data at index 1,2,3,4 index.
Step 2: Search for key in knowledge
- Iterate through the key-value list and find name associated with bob.
- Replace (name) with bob.
- Updated string so far: bobis(age)yearsold
Step 3: Continue scanning s
- Encounter ( at index 8.
- Extract key age from s[9:12].
Step 4: Search for key in knowledge
- Iterate through the key-value list and find age associated with two.
- Replace (age) with two.
- Updated string so far: bobistwoyearsold
Output:
bobistwoyearsold
Code for All Languages
C++
string evaluate(string s, vector<vector<string>>& knowledge) {
string result;
int n = s.length();
// Taking input knowledge into a vector for brute force search
vector<pair<string, string>> knowledgeList;
for (auto &entry : knowledge) {
knowledgeList.push_back({entry[0], entry[1]});
}
for (int i = 0; i < n; ++i) {
if (s[i] == '(') { // Find an opening bracket
int j = i + 1;
while (j < n && s[j] != ')') j++; // Find closing bracket
string key = s.substr(i + 1, j - i - 1);
string value = "?"; // Default to "?" if key is not found
// Brute force search in knowledge list
for (auto &pair : knowledgeList) {
if (pair.first == key) {
value = pair.second;
break;
}
}
result += value; // Append the value to result
i = j; // Skip to the end of this bracket pair
} else {
result += s[i]; // Append normal characters
}
}
return result;
}Java
class Solution {
public String evaluate(String s, List<List<String>> knowledge) {
StringBuilder result = new StringBuilder();
int n = s.length();
// Taking input knowledge into a list for brute force search
List<Map.Entry<String, String>> knowledgeList = new ArrayList<>();
for (List<String> entry : knowledge) {
knowledgeList.add(new AbstractMap.SimpleEntry<>(entry.get(0), entry.get(1)));
}
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '(') { // Find an opening bracket
int j = i + 1;
while (j < n && s.charAt(j) != ')') j++; // Find closing bracket
String key = s.substring(i + 1, j);
String value = "?"; // Default to "?" if key is not found
// Brute force search in knowledge list
for (Map.Entry<String, String> pair : knowledgeList) {
if (pair.getKey().equals(key)) {
value = pair.getValue();
break;
}
}
result.append(value); // Append the value to result
i = j; // Skip to the end of this bracket pair
} else {
result.append(s.charAt(i)); // Append normal characters
}
}
return result.toString();
}
}Python
import sys
def evaluate(s, knowledge):
result = []
n = len(s)
# Taking input knowledge into a dictionary for brute force search
knowledge_dict = {entry[0]: entry[1] for entry in knowledge}
i = 0
while i < n:
if s[i] == '(':
j = i + 1
while j < n and s[j] != ')':
j += 1
key = s[i + 1:j]
value = knowledge_dict.get(key, "?") # Default to "?" if key is not found
result.append(value) # Append the value to result
i = j # Skip to the end of this bracket pair
else:
result.append(s[i]) # Append normal characters
i += 1
return "".join(result)JavaScript
Evaluate the Bracket Pairs of a String - Brute Force - Javascript
function evaluate(s, knowledge) {
let result = "";
let n = s.length;
// Taking input knowledge into a map for brute force search
let knowledgeMap = new Map(knowledge.map(([key, value]) => [key, value]));
let i = 0;
while (i < n) {
if (s[i] === '(') {
let j = i + 1;
while (j < n && s[j] !== ')') {
j++;
}
let key = s.substring(i + 1, j);
let value = knowledgeMap.has(key) ? knowledgeMap.get(key) : "?"; // Default to "?" if key is not found
result += value; // Append the value to result
i = j; // Skip to the end of this bracket pair
} else {
result += s[i]; // Append normal characters
}
i++;
}
return result;
}Bridge between Brute force and Optimized
In the brute force approach, we iterate through the string s, extract bracketed keys, and search for each key by scanning the knowledge list one by one. This requires checking each key-value pair manually every time a key is encountered, leading to unnecessary repeated searches.
To optimize, we store the key-value pairs in a hash map, which allows for direct key lookups in O(1) time instead of scanning the list every time. This eliminates redundant searches and significantly improves efficiency by reducing repeated iterations over the key-value list. By leveraging a hash map, we transition from sequential searching to constant-time lookups, making the approach scalable and performant.
Optimized Approach
Intuition
The intuition behind the solution is to perform a linear scan of the string s, using a variable i to keep track of our position. We proceed through the string character by character until we encounter an opening bracket (.
When an opening bracket is detected, we know that a key is started. We then find the closing bracket ) that pairs with the opening bracket. The substring within the brackets is the key we are interested in.
We check the dictionary d we've made from the knowledge array to see if the key exists:
- If the key has a corresponding value in d, we add that value to the result string.
- If the key does not exist in d, we append a question mark ? to the result string.
Once we have replaced the key with its value or a question mark, we move i to the position just after the closing bracket since all characters within the brackets have been processed.
If we encounter any character other than an opening bracket, we simply add that character to the result string, as it does not need any substitution.
Our process continues until we've scanned all characters within the string s. In the end, we join all parts of our result list into a single string and return it as the solution.
Approach
The solution leverages a dictionary and simple string traversal to effectively solve the problem. The approach follows these steps:
- Convert the knowledge list of lists into a dictionary where each key-value pair is one key from the bracket pairs and its corresponding value. This allows for constant-time access to the values while we traverse the string s.
- Initialize an index i to start at the first character of the string s and a ans list to hold the parts of the new string we're building.
- Start iterating over the string s using i. We need to check each character and decide what to do:
- If the current character is an opening bracket '(', we must find the matching closing bracket ')' to identify the key within.
- We use the find() method to locate the index j of the closing bracket.
- Obtain the key by slicing the string s from i + 1 to j to get the content within brackets.
- Use the key to look up the value in the dictionary d. If the key is found, append the value to the ans list; otherwise, append a question mark '?'.
- Update the index i to move past the closing bracket.
- If the current character isn't an opening bracket, append it directly to the ans list because it's part of the final string.
- Increment i to continue to the next character.
- After the while loop completes, we will have iterated over the entire string, replacing all bracketed keys with their corresponding values or a question mark.
- Finally, join the elements of the ans list into a string:
Let us understand this with a video,
Evaluate the Bracket Pairs of a String-Optimal-Approach
Dry Run
Let's go through an example to illustrate the solution approach. Suppose we have the following string s and knowledge base:
s = "Hi, my name is (name) and I am (age) years old." knowledge = [["name","Bob"], ["age","25"]]
First, we convert the knowledge list into a dictionary, d:
d = {"name": "Bob", "age": "25"}
Now, we initialize our starting index i = 0, and an empty list ans = [] to store parts of our new string.
We begin iterating over the string s. The first characters "Hi, my name is " are not within brackets, so we add them directly to ans.
At index 15, we encounter an opening bracket (. Now we need to find the corresponding closing bracket ):
- We use s.find(')', i + 1) and find the closing bracket at index 20.
- The key within the brackets is s[i + 1 : j], which yields "name".
- We search for "name" in d and find that it corresponds to the value "Bob".
- ans.append(d.get(key, '?')) will result in appending "Bob" to ans.
Next, we update i to be just past the closing bracket; i = 20.
Continuing to iterate, we add the characters " and I am " directly to ans, as they are outside of brackets.
Upon reaching the next opening bracket at index 31, we repeat the process:
- We find the closing bracket at index 35.
- We identify the key as "age".
- We search for "age" and obtain the value "25" from d.
- We append "25" to ans.
Finally, i is updated to index 36, and we add the remaining characters " years old." to ans.
After processing the entire string, we join all parts of ans using ''.join(ans) to get the final string:
"Hi, my name is Bob and I am 25 years old."
This is the string with the keys in the original string s replaced by their corresponding values from the knowledge base, which is the desired outcome. If at any point a key had not been found in d, a '?' would have been appended instead.
Cpp
// Evaluate the Bracket Pairs of a String - Optimized Approach - Cpp
class Solution {
public:
string evaluate(string s, unordered_map<string, string>& knowledgeMap) {
string result;
int n = s.size();
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
int j = i + 1;
while (j < n && s[j] != ')') j++;
string key = s.substr(i + 1, j - i - 1);
result += knowledgeMap.count(key) ? knowledgeMap[key] : "?";
i = j; // Move to closing bracket
} else {
result += s[i];
}
}
return result;
}
};Java
//Evaluate the Bracket Pairs of a String - Optimized Approach - Java
import java.util.*;
class Solution {
public String evaluate(String s, Map<String, String> knowledgeMap) {
StringBuilder result = new StringBuilder();
int n = s.length();
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '(') {
int j = i + 1;
while (j < n && s.charAt(j) != ')') j++;
String key = s.substring(i + 1, j);
result.append(knowledgeMap.getOrDefault(key, "?"));
i = j; // Move to closing bracket
} else {
result.append(s.charAt(i));
}
}
return result.toString();
}
}Python
#Evaluate the Bracket Pairs of a String - Optimized Approach - Python
def evaluate(s, knowledge):
result = []
n = len(s)
# Convert knowledge list into a dictionary for O(1) lookups
knowledge_dict = dict(knowledge)
i = 0
while i < n:
if s[i] == '(':
j = i + 1
while j < n and s[j] != ')':
j += 1
key = s[i + 1:j]
result.append(knowledge_dict.get(key, "?")) # Replace key or default to "?"
i = j # Skip to closing bracket
else:
result.append(s[i]) # Append normal characters
i += 1
return "".join(result)Javascript
//Evaluate the Bracket Pairs of a String - Optimized Approach - Javascript
function evaluate(s, knowledge) {
let result = "";
let n = s.length;
// Convert knowledge list into a Map for O(1) lookups
let knowledgeMap = new Map(knowledge.map(([key, value]) => [key, value]));
let i = 0;
while (i < n) {
if (s[i] === "(") {
let j = i + 1;
while (j < n && s[j] !== ')') {
j++;
}
let key = s.substring(i + 1, j);
result += knowledgeMap.has(key) ? knowledgeMap.get(key) : "?"; // Replace key or default to "?"
i = j; // Skip to closing bracket
} else {
result += s[i]; // Append normal characters
}
i++;
}
return result;
}Time Complexity - Evaluate the Bracket Pairs of a String - O (m+n)
The optimized approach efficiently scans the input string s in a single pass (O(n)), processing each character once. When encountering a key inside parentheses, it extracts and looks up its corresponding value in a hash map, which provides O(1) average-time complexity for key retrieval. Constructing the hash map from the knowledge list requires O(m) time, where m is the number of key-value pairs. Since both steps run independently, the overall time complexity is O(n + m), making the solution optimal even for large inputs.
Space complexity - Evaluate the Bracket Pairs of a String - O(m+n)
The approach requires O(m) space for storing key-value pairs in the hash map, as each unique key from the knowledge list is stored once. Additionally, the result string requires O(n) space, as it stores a modified version of s with all bracketed keys replaced. Temporary variables used for iteration contribute O(1) additional space. Thus, the total space complexity is O(n + m), ensuring that the solution remains efficient in terms of memory usage.
Similar questions
Constructs a frequency map of characters and checks if words can be formed using it.
Uses a dictionary of root words to replace words in a sentence with their shortest match.