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.
class Solution:
def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
def find_right_bracket(s, start, end):
for i in range(start, end):
if s[i] == ')':
return i
knowledge_dict = {item[0]: item[1] for item in knowledge}
res, n = [], len(s)
i = 0
while i < n:
if s[i] == '(':
right_bracket_pos = find_right_bracket(s, i + 1, n)
key = s[i + 1: right_bracket_pos]
res.append(knowledge_dict.get(key, '?'))
i = right_bracket_pos + 1
else:
res.append(s[i])
i += 1
return ''.join(res)
class Solution {
public String evaluate(String s, List<List<String>> knowledge) {
Map<String, String> knowledgeDict = new HashMap<>();
for (List<String> item : knowledge) {
knowledgeDict.put(item.get(0), item.get(1));
}
StringBuilder res = new StringBuilder();
int i = 0, n = s.length();
while (i < n) {
if (s.charAt(i) == '(') {
int rightBracketPos = findRightBracket(s, i + 1, n);
String key = s.substring(i + 1, rightBracketPos);
res.append(knowledgeDict.getOrDefault(key, "?"));
i = rightBracketPos + 1;
} else {
res.append(s.charAt(i));
i += 1;
}
}
return res.toString();
}
private int findRightBracket(String s, int start, int end) {
for (int i = start; i < end; ++i) {
if (s.charAt(i) == ')') {
return i;
}
}
return -1;
}
}