1807. Evaluate the Bracket Pairs of a String LeetCode Solution
In this guide, you will get 1807. Evaluate the Bracket Pairs of a String LeetCode Solution with the best time and space complexity. The solution to Evaluate the Bracket Pairs of a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Evaluate the Bracket Pairs of a String
You are given a string s 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] = [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:
Replace keyi and the bracket pair with the key’s corresponding valuei.
If you do not know the value of the key, you will replace 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.
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 <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1 <= keyi.length, valuei.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.
keyi and valuei consist of lowercase English letters.
Each keyi in knowledge is unique.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1807. Evaluate the Bracket Pairs of a String LeetCode Solution in C++
class Solution {
public:
string evaluate(string s, vector<vector<string>>& knowledge) {
string ans;
unordered_map<string, string> map;
for (const vector<string>& list : knowledge)
map["(" + list[0] + ")"] = list[1];
for (int i = 0; i < s.length(); ++i) {
const char c = s[i];
if (c == '(') {
const int j = s.find_first_of(')', i);
const string& key = s.substr(i, j - i + 1);
ans += map.contains(key) ? map[key] : "?";
i = j;
} else {
ans += c;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1807. Evaluate the Bracket Pairs of a String LeetCode Solution in Java
class Solution {
public String evaluate(String s, List<List<String>> knowledge) {
StringBuilder sb = new StringBuilder();
Map<String, String> map = new HashMap<>();
for (List<String> list : knowledge)
map.put("(" + list.get(0) + ")", list.get(1));
for (int i = 0; i < s.length(); ++i) {
final char c = s.charAt(i);
if (c == '(') {
final int j = s.indexOf(')', i);
sb.append(map.getOrDefault(s.substring(i, j + 1), "?"));
i = j;
} else {
sb.append(c);
}
}
return sb.toString();
}
} // code provided by PROGIEZ
1807. Evaluate the Bracket Pairs of a String LeetCode Solution in Python
