Problem

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 evaluatingall of the bracket pairs.

Examples

Example 1

1
2
3
4
5

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

1
2
3

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

1
2
3
4
5

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 <= 10^5
  • 0 <= knowledge.length <= 10^5
  • 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.

Solution

Method 1 – Hash Map Lookup and String Building

Intuition

We can use a hash map to store the key-value pairs from knowledge. As we scan the string, whenever we find a bracket pair, we extract the key and replace it with its value from the map (or ? if not found).

Approach

  1. Build a dictionary from knowledge for O(1) key lookup.
  2. Iterate through the string s:
    • If a ( is found, extract the key until ).
    • Replace the bracketed key with its value from the dictionary, or ? if not found.
    • Otherwise, add the character to the result.
  3. Return the built result string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> mp;
        for (auto& kv : knowledge) mp[kv[0]] = kv[1];
        string ans, key;
        bool in_bracket = false;
        for (char c : s) {
            if (c == '(') {
                in_bracket = true;
                key.clear();
            } else if (c == ')') {
                ans += mp.count(key) ? mp[key] : "?";
                in_bracket = false;
            } else if (in_bracket) {
                key += c;
            } else {
                ans += c;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func evaluate(s string, knowledge [][]string) string {
    mp := map[string]string{}
    for _, kv := range knowledge {
        mp[kv[0]] = kv[1]
    }
    ans := ""
    inBracket := false
    key := ""
    for _, c := range s {
        if c == '(' {
            inBracket = true
            key = ""
        } else if c == ')' {
            if v, ok := mp[key]; ok {
                ans += v
            } else {
                ans += "?"
            }
            inBracket = false
        } else if inBracket {
            key += string(c)
        } else {
            ans += string(c)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> mp = new HashMap<>();
        for (List<String> kv : knowledge) mp.put(kv.get(0), kv.get(1));
        StringBuilder ans = new StringBuilder();
        StringBuilder key = new StringBuilder();
        boolean inBracket = false;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                inBracket = true;
                key.setLength(0);
            } else if (c == ')') {
                ans.append(mp.getOrDefault(key.toString(), "?"));
                inBracket = false;
            } else if (inBracket) {
                key.append(c);
            } else {
                ans.append(c);
            }
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun evaluate(s: String, knowledge: List<List<String>>): String {
        val mp = knowledge.associate { it[0] to it[1] }
        val ans = StringBuilder()
        var inBracket = false
        val key = StringBuilder()
        for (c in s) {
            when {
                c == '(' -> {
                    inBracket = true
                    key.clear()
                }
                c == ')' -> {
                    ans.append(mp[key.toString()] ?: "?")
                    inBracket = false
                }
                inBracket -> key.append(c)
                else -> ans.append(c)
            }
        }
        return ans.toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
        mp = {k: v for k, v in knowledge}
        ans = []
        i = 0
        n = len(s)
        while i < n:
            if s[i] == '(': 
                j = i + 1
                while s[j] != ')':
                    j += 1
                key = s[i+1:j]
                ans.append(mp.get(key, '?'))
                i = j + 1
            else:
                ans.append(s[i])
                i += 1
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn evaluate(s: String, knowledge: Vec<Vec<String>>) -> String {
        use std::collections::HashMap;
        let mp: HashMap<&str, &str> = knowledge.iter().map(|kv| (kv[0].as_str(), kv[1].as_str())).collect();
        let mut ans = String::new();
        let mut key = String::new();
        let mut in_bracket = false;
        for c in s.chars() {
            if c == '(' {
                in_bracket = true;
                key.clear();
            } else if c == ')' {
                ans.push_str(mp.get(key.as_str()).unwrap_or(&"?"));
                in_bracket = false;
            } else if in_bracket {
                key.push(c);
            } else {
                ans.push(c);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    evaluate(s: string, knowledge: string[][]): string {
        const mp = new Map(knowledge.map(([k, v]) => [k, v]));
        let ans = "";
        let inBracket = false;
        let key = "";
        for (const c of s) {
            if (c === '(') {
                inBracket = true;
                key = "";
            } else if (c === ')') {
                ans += mp.has(key) ? mp.get(key) : "?";
                inBracket = false;
            } else if (inBracket) {
                key += c;
            } else {
                ans += c;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the length of s and m is the total length of all keys.
  • 🧺 Space complexity: O(m) for the hash map and result string.