LeetCode 1807. 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 correspondingvaluei
.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.
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.
Example 4:
Input: s = "(a)(b)", knowledge = [["a","b"],["b","a"]]
Output: "ba"
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
'('
ins
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
andvaluei
consist of lowercase English letters.Each
keyi
inknowledge
is unique.
Solution
class Solution {
public:
string evaluate(string s, vector<vector<string>>& knowledge) {
map<string, string> mymap;
for (const vector<string>& k : knowledge) {
mymap[k[0]] = k[1];
}
string ans;
string key;
bool in_bracket = false;
for (char ch : s) {
if (ch == '(') {
in_bracket = true;
} else if (ch == ')') {
in_bracket = false;
if (mymap.count(key) > 0) {
ans += mymap[key];
} else {
ans += "?";
}
key.clear();
} else {
if (in_bracket) {
key += ch;
} else {
ans += ch;
}
}
}
return ans;
}
};
Last updated
Was this helpful?