Leetcode 1807. Evaluate the Bracket Pairs of a String Solution
Problem Explanation
You are given a string s containing bracket pairs. Each bracket pair contains a non-empty key. Your goal is to evaluate all the bracket pairs and replace them with their corresponding values provided in the knowledge array. If a key does not have a value in the knowledge array, replace the bracket pair with a question mark.
Let's understand the problem with an example:
Given s = "(name)is(age)yearsold" and knowledge = [["name","bob"],["age","two"]]. Since "name" has a value "bob" and "age" has a value "two", we replace them to get "bobistwoyearsold".
Approach
We will use the following steps to solve the problem:
- Create an unordered map and store the keys and their corresponding values from 'knowledge' in the unordered map.
- Initialize an empty answer string
ans. - Iterate through the string, and for every character:
- If the character is an open bracket symbol '(':
- Find the closing bracket symbol ')' for this bracket pair.
- Create a key from the current bracket pair.
- Check if the key is present in the unordered map.
- If it is, append the corresponding value from the map to the
ans; otherwise, append '?'. - Update the index variable
ito skip the key and both brackets.
- Else, append the character to the
ans.
- If the character is an open bracket symbol '(':
- Return the
ansstring.
Example
Let's walk through the algorithm using the same example we used before:
s = "(name)is(age)yearsold" and knowledge = [["name","bob"],["age","two"]].
-
Create an unordered map from the
knowledgearray:map = { "(name)": "bob", "(age)": "two"} -
Initialize
ansas an empty string:ans = "". -
Iterate through the string:
- i=0, s[i]='(', find the closing bracket j=5, key="(name)", append "bob" to
ans. - Update i=5, move to next character.
- i=6, s[i]='i', append 'i' to
ans. - i=7, s[i]='s', append 's' to
ans. - i=8, s[i]='(', find the closing bracket j=12, key="(age)", append "two" to
ans. - Update i=12, move to next character.
- i=13, s[i]='y', append 'y' to
ans. - i=14, s[i]='e', append 'e' to
ans. - i=15, s[i]='a', append 'a' to
ans. - i=16, s[i]='r', append 'r' to
ans. - i=17, s[i]='s', append 's' to
ans. - i=18, s[i]='o', append 'o' to
ans. - i=19, s[i]='l', append 'l' to
ans. - i=20, s[i]='d', append 'd' to
ans.
- i=0, s[i]='(', find the closing bracket j=5, key="(name)", append "bob" to
-
The final answer is "bobistwoyearsold".
Python Solution
1class Solution:
2 def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
3 ans = ""
4 m = {}
5
6 for key, value in knowledge:
7 m[f"({key})"] = value
8
9 i = 0
10 while i < len(s):
11 if s[i] == '(':
12 j = s.index(')', i)
13 key = s[i:j+1]
14 ans += m.get(key, "?")
15 i = j + 1
16 else:
17 ans += s[i]
18 i += 1
19
20 return ans
Java Solution
1class Solution {
2 public String evaluate(String s, String[][] knowledge) {
3 StringBuilder ans = new StringBuilder();
4 HashMap<String, String> map = new HashMap<>();
5
6 for (String[] pair : knowledge) {
7 map.put("(" + pair[0] + ")", pair[1]);
8 }
9
10 for (int i = 0; i < s.length(); ++i) {
11 char c = s.charAt(i);
12 if (c == '(') {
13 int j = s.indexOf(')', i);
14 String key = s.substring(i, j+1);
15 ans.append(map.getOrDefault(key, "?"));
16 i = j;
17 } else {
18 ans.append(c);
19 }
20 }
21
22 return ans.toString();
23 }
24}
Javascript Solution
1class Solution {
2 evaluate(s, knowledge) {
3 let ans = "";
4 let m = new Map();
5
6 for (let [key, value] of knowledge) {
7 m.set(`(${key})`, value);
8 }
9
10 for (let i = 0; i < s.length; ++i) {
11 const c = s[i];
12 if (c === '(') {
13 const j = s.indexOf(')', i);
14 const key = s.substring(i, j + 1);
15 ans += m.has(key) ? m.get(key) : "?";
16 i = j;
17 } else {
18 ans += c;
19 }
20 }
21
22 return ans;
23 }
24}
C++ Solution
1class Solution {
2public:
3 string evaluate(string s, vector<vector<string>>& knowledge) {
4 string ans;
5 unordered_map<string, string> map;
6
7 for (const vector<string>& list : knowledge) {
8 map["(" + list[0] + ")"] = list[1];
9 }
10
11 for (int i = 0; i < s.length(); ++i) {
12 const char c = s[i];
13 if (c == '(') {
14 const int j = s.find_first_of(')', i);
15 const string& key = s.substr(i, j - i + 1);
16 ans += map.count(key) ? map[key] : "?";
17 i = j;
18 } else {
19 ans += c;
20 }
21 }
22
23 return ans;
24 }
25};
C# Solution
1public class Solution {
2 public string Evaluate(string s, string[][] knowledge) {
3 StringBuilder ans = new StringBuilder();
4 Dictionary<string, string> map = new Dictionary<string, string>();
5
6 foreach (string[] pair in knowledge) {
7 map[$"({pair[0]})"] = pair[1];
8 }
9
10 for (int i = 0; i < s.Length; ++i) {
11 char c = s[i];
12 if (c == '(') {
13 int j = s.IndexOf(')', i);
14 string key = s.Substring(i, j - i + 1);
15 ans.Append(map.ContainsKey(key) ? map[key] : "?");
16 i = j;
17 } else {
18 ans.Append(c);
19 }
20 }
21
22 return ans.ToString();
23 }
24}
Conclusion
In this article, we have discussed how to solve the problem of evaluating string expressions containing bracket pairs and keys that needed to be replaced by their corresponding values from an array. We provided step-by-step explanations and implementations for the solution in Python, Java, JavaScript, C++, and C#.
Using a HashMap or an unordered_map and StringBuilder or just a simple string, we can efficiently replace the keys with their corresponding values or '?' if the value is not present in constant time. Make sure to practice and understand each implementation for a better conceptual understanding of the problem and its solutions.