Formatted question description: https://leetcode.ca/all/1807.html
1807. Evaluate the Bracket Pairs of a String
Level
Medium
Description
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] = [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 correspondingvalue_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 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 <= 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
'('
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
. key_i
andvalue_i
consist of lowercase English letters.- Each
key_i
inknowledge
is unique.
Solution
First use a map to store all key-value pairs in knowledge
. Then loop over s
and generate the evaluated string. If the current position is out of brackets, simply append the current character to the evaluated string. Otherwise, find the key, get the value from the map and append the value to the evaluated string, or append "?"
to the evaluated string if the key does not exist in the map. Finally, return the evaluated string.
class Solution {
public String evaluate(String s, List<List<String>> knowledge) {
Map<String, String> map = new HashMap<String, String>();
for (List<String> entry : knowledge) {
String key = entry.get(0), value = entry.get(1);
map.put(key, value);
}
StringBuffer sb = new StringBuffer();
boolean inBracket = false;
int start = -1;
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == '(') {
inBracket = true;
start = i + 1;
} else if (c == ')') {
inBracket = false;
String key = s.substring(start, i);
String value = map.getOrDefault(key, "?");
sb.append(value);
} else if (!inBracket)
sb.append(c);
}
return sb.toString();
}
}