Leetcode 1807. Evaluate the Bracket Pairs of a String Solution

Problem Explanation

You are given a string s containing bracket pairs. Each bracket pair contains a non-empty key. Your goal is to evaluate all the bracket pairs and replace them with their corresponding values provided in the knowledge array. If a key does not have a value in the knowledge array, replace the bracket pair with a question mark.

Let's understand the problem with an example:

Given s = "(name)is(age)yearsold" and knowledge = [["name","bob"],["age","two"]]. Since "name" has a value "bob" and "age" has a value "two", we replace them to get "bobistwoyearsold".

Approach

We will use the following steps to solve the problem:

  1. Create an unordered map and store the keys and their corresponding values from 'knowledge' in the unordered map.
  2. Initialize an empty answer string ans.
  3. Iterate through the string, and for every character:
    • If the character is an open bracket symbol '(':
      • Find the closing bracket symbol ')' for this bracket pair.
      • Create a key from the current bracket pair.
      • Check if the key is present in the unordered map.
      • If it is, append the corresponding value from the map to the ans; otherwise, append '?'.
      • Update the index variable i to skip the key and both brackets.
    • Else, append the character to the ans.
  4. Return the ans string.

Example

Let's walk through the algorithm using the same example we used before:

s = "(name)is(age)yearsold" and knowledge = [["name","bob"],["age","two"]].

  1. Create an unordered map from the knowledge array:

    map = { "(name)": "bob", "(age)": "two"}

  2. Initialize ans as an empty string: ans = "".

  3. Iterate through the string:

    • i=0, s[i]='(', find the closing bracket j=5, key="(name)", append "bob" to ans.
    • Update i=5, move to next character.
    • i=6, s[i]='i', append 'i' to ans.
    • i=7, s[i]='s', append 's' to ans.
    • i=8, s[i]='(', find the closing bracket j=12, key="(age)", append "two" to ans.
    • Update i=12, move to next character.
    • i=13, s[i]='y', append 'y' to ans.
    • i=14, s[i]='e', append 'e' to ans.
    • i=15, s[i]='a', append 'a' to ans.
    • i=16, s[i]='r', append 'r' to ans.
    • i=17, s[i]='s', append 's' to ans.
    • i=18, s[i]='o', append 'o' to ans.
    • i=19, s[i]='l', append 'l' to ans.
    • i=20, s[i]='d', append 'd' to ans.
  4. The final answer is "bobistwoyearsold".

Python Solution

1class Solution:
2    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
3        ans = ""
4        m = {}
5        
6        for key, value in knowledge:
7            m[f"({key})"] = value
8            
9        i = 0
10        while i < len(s):
11            if s[i] == '(':
12                j = s.index(')', i)
13                key = s[i:j+1]
14                ans += m.get(key, "?")
15                i = j + 1
16            else:
17                ans += s[i]
18                i += 1
19                
20        return ans

Java Solution

1class Solution {
2    public String evaluate(String s, String[][] knowledge) {
3        StringBuilder ans = new StringBuilder();
4        HashMap<String, String> map = new HashMap<>();
5
6        for (String[] pair : knowledge) {
7            map.put("(" + pair[0] + ")", pair[1]);
8        }
9
10        for (int i = 0; i < s.length(); ++i) {
11            char c = s.charAt(i);
12            if (c == '(') {
13                int j = s.indexOf(')', i);
14                String key = s.substring(i, j+1);
15                ans.append(map.getOrDefault(key, "?"));
16                i = j;
17            } else {
18                ans.append(c);
19            }
20        }
21
22        return ans.toString();
23    }
24}

Javascript Solution

1class Solution {
2    evaluate(s, knowledge) {
3        let ans = "";
4        let m = new Map();
5
6        for (let [key, value] of knowledge) {
7            m.set(`(${key})`, value);
8        }
9
10        for (let i = 0; i < s.length; ++i) {
11            const c = s[i];
12            if (c === '(') {
13                const j = s.indexOf(')', i);
14                const key = s.substring(i, j + 1);
15                ans += m.has(key) ? m.get(key) : "?";
16                i = j;
17            } else {
18                ans += c;
19            }
20        }
21
22        return ans;
23    }
24}

C++ Solution

1class Solution {
2public:
3    string evaluate(string s, vector<vector<string>>& knowledge) {
4        string ans;
5        unordered_map<string, string> map;
6
7        for (const vector<string>& list : knowledge) {
8            map["(" + list[0] + ")"] = list[1];
9        }
10
11        for (int i = 0; i < s.length(); ++i) {
12            const char c = s[i];
13            if (c == '(') {
14                const int j = s.find_first_of(')', i);
15                const string& key = s.substr(i, j - i + 1);
16                ans += map.count(key) ? map[key] : "?";
17                i = j;
18            } else {
19                ans += c;
20            }
21        }
22
23        return ans;
24    }
25};

C# Solution

1public class Solution {
2    public string Evaluate(string s, string[][] knowledge) {
3        StringBuilder ans = new StringBuilder();
4        Dictionary<string, string> map = new Dictionary<string, string>();
5
6        foreach (string[] pair in knowledge) {
7            map[$"({pair[0]})"] = pair[1];
8        }
9
10        for (int i = 0; i < s.Length; ++i) {
11            char c = s[i];
12            if (c == '(') {
13                int j = s.IndexOf(')', i);
14                string key = s.Substring(i, j - i + 1);
15                ans.Append(map.ContainsKey(key) ? map[key] : "?");
16                i = j;
17            } else {
18                ans.Append(c);
19            }
20        }
21
22        return ans.ToString();
23    }
24}

Conclusion

In this article, we have discussed how to solve the problem of evaluating string expressions containing bracket pairs and keys that needed to be replaced by their corresponding values from an array. We provided step-by-step explanations and implementations for the solution in Python, Java, JavaScript, C++, and C#.

Using a HashMap or an unordered_map and StringBuilder or just a simple string, we can efficiently replace the keys with their corresponding values or '?' if the value is not present in constant time. Make sure to practice and understand each implementation for a better conceptual understanding of the problem and its solutions.