LeetCode 1807: Evaluate the Bracket Pairs of a String

Explanation:

We can solve this problem using a HashMap to store the key-value pairs from the knowledge array. Then, we can iterate through the string and whenever we encounter a bracket pair, we can check if the key exists in our HashMap. If it does, we replace the bracket pair with the corresponding value; otherwise, we replace it with a question mark.

Algorithm:

1. Create a HashMap to store the key-value pairs from the knowledge array.
2. Iterate through the string:
   • If an opening bracket is found, extract the key until the closing bracket.
   • Check if the key exists in the HashMap.
   • Replace the bracket pair with the corresponding value or a question mark.
3. Return the modified string.

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input string.

Space Complexity:

The space complexity is O(k), where k is the number of unique keys in the knowledge array.

:

class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> map = new HashMap<>();
        for (List<String> pair : knowledge) {
            map.put(pair.get(0), pair.get(1));
        }
        
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            char c = s.charAt(i);
            if (c == '(') {
                int j = i + 1;
                while (s.charAt(j) != ')') {
                    j++;
                }
                String key = s.substring(i + 1, j);
                sb.append(map.getOrDefault(key, "?"));
                i = j + 1;
            } else {
                sb.append(c);
                i++;
            }
        }
        
        return sb.toString();
    }
}