You are given a string s
that contains some bracket pairs, with each pair containing a non-empty key.
"(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:
keyi
and the bracket pair with the key's corresponding valuei
.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 ')'
.'('
in s
will have a corresponding close bracket ')'
.s
will be non-empty.s
.keyi
and valuei
consist of lowercase English letters.keyi
in knowledge
is unique.struct Solution;
use std::collections::HashMap;
impl Solution {
fn evaluate(s: String, knowledge: Vec<Vec<String>>) -> String {
let mut hm: HashMap<String, String> = HashMap::new();
for pair in knowledge {
hm.insert(pair[0].to_string(), pair[1].to_string());
}
let mut res = "".to_string();
let s: Vec<char> = s.chars().collect();
let n = s.len();
let mut bracket = false;
let mut temp = vec![];
for i in 0..n {
match s[i] {
'(' => {
bracket = true;
}
')' => {
bracket = false;
let key: String = temp.iter().collect();
if let Some(value) = hm.get(&key) {
res.push_str(value);
} else {
res.push('?');
}
temp = vec![];
}
_ => {
if bracket {
temp.push(s[i]);
} else {
res.push(s[i])
}
}
}
}
res
}
}
#[test]
fn test() {
let s = "(name)is(age)yearsold".to_string();
let knowledge = vec_vec_string![["name", "bob"], ["age", "two"]];
let res = "bobistwoyearsold".to_string();
assert_eq!(Solution::evaluate(s, knowledge), res);
let s = "hi(name)".to_string();
let knowledge = vec_vec_string![["a", "b"]];
let res = "hi?".to_string();
assert_eq!(Solution::evaluate(s, knowledge), res);
let s = "(a)(a)(a)aaa".to_string();
let knowledge = vec_vec_string![["a", "yes"]];
let res = "yesyesyesaaa".to_string();
assert_eq!(Solution::evaluate(s, knowledge), res);
let s = "(a)(b)".to_string();
let knowledge = vec_vec_string![["a", "b"], ["b", "a"]];
let res = "ba".to_string();
assert_eq!(Solution::evaluate(s, knowledge), res);
}