1807. Evaluate the Bracket Pairs of a String

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 corresponding value_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.

Constraints:

1 <= s.length <= 10⁵
0 <= knowledge.length <= 10⁵
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 '(' 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.
key_i and value_i consist of lowercase English letters.
Each key_i in knowledge is unique.

Solutions

Solution 1: Hash Table + Simulation

First, we use a hash table $d$ to record the key-value pairs in knowledge.

Then we traverse the string $s$. If the current character is an open parenthesis '(', we start traversing from the current position until we encounter a close parenthesis ')'. At this point, the string within the parentheses is the key. We look for the corresponding value of this key in the hash table $d$. If found, we replace the value within the parentheses with it, otherwise, we replace it with '?'.

The time complexity is $O(n + m)$, and the space complexity is $O(L)$. Here, $n$ and $m$ are the lengths of the string $s$ and the list knowledge respectively, and $L$ is the sum of the lengths of all strings in knowledge.

Python3JavaC++GoTypeScriptRust

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        d = {a: b for a, b in knowledge}
        i, n = 0, len(s)
        ans = []
        while i < n:
            if s[i] == '(':
                j = s.find(')', i + 1)
                ans.append(d.get(s[i + 1 : j], '?'))
                i = j
            else:
                ans.append(s[i])
            i += 1
        return ''.join(ans)

class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> d = new HashMap<>(knowledge.size());
        for (var e : knowledge) {
            d.put(e.get(0), e.get(1));
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                int j = s.indexOf(')', i + 1);
                ans.append(d.getOrDefault(s.substring(i + 1, j), "?"));
                i = j;
            } else {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> d;
        for (auto& e : knowledge) {
            d[e[0]] = e[1];
        }
        string ans;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                int j = s.find(")", i + 1);
                auto t = s.substr(i + 1, j - i - 1);
                ans += d.count(t) ? d[t] : "?";
                i = j;
            } else {
                ans += s[i];
            }
        }
        return ans;
    }
};

func evaluate(s string, knowledge [][]string) string {
    d := map[string]string{}
    for _, v := range knowledge {
        d[v[0]] = v[1]
    }
    var ans strings.Builder
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            j := i + 1
            for s[j] != ')' {
                j++
            }
            if v, ok := d[s[i+1:j]]; ok {
                ans.WriteString(v)
            } else {
                ans.WriteByte('?')
            }
            i = j
        } else {
            ans.WriteByte(s[i])
        }
    }
    return ans.String()
}

function evaluate(s: string, knowledge: string[][]): string {
    const n = s.length;
    const map = new Map();
    for (const [k, v] of knowledge) {
        map.set(k, v);
    }
    const ans = [];
    let i = 0;
    while (i < n) {
        if (s[i] === '(') {
            const j = s.indexOf(')', i + 1);
            ans.push(map.get(s.slice(i + 1, j)) ?? '?');
            i = j;
        } else {
            ans.push(s[i]);
        }
        i++;
    }
    return ans.join('');
}

use std::collections::HashMap;
impl Solution {
    pub fn evaluate(s: String, knowledge: Vec<Vec<String>>) -> String {
        let s = s.as_bytes();
        let n = s.len();
        let mut map = HashMap::new();
        for v in knowledge.iter() {
            map.insert(&v[0], &v[1]);
        }
        let mut ans = String::new();
        let mut i = 0;
        while i < n {
            if s[i] == b'(' {
                i += 1;
                let mut j = i;
                let mut key = String::new();
                while s[j] != b')' {
                    key.push(s[j] as char);
                    j += 1;
                }
                ans.push_str(map.get(&key).unwrap_or(&&'?'.to_string()));
                i = j;
            } else {
                ans.push(s[i] as char);
            }
            i += 1;
        }
        ans
    }
}

1807. Evaluate the Bracket Pairs of a String

Description

Solutions

Solution 1: Hash Table + Simulation

Comments