1807. Evaluate the Bracket Pairs of a String

Problem Description

Given a string s containing bracket pairs with keys inside and a 2D string array knowledge where each knowledge[i] = [key<sub>i</sub>, value<sub>i</sub>], evaluate all bracket pairs in s. If a key within a bracket pair is found in knowledge, replace the bracket pair with its corresponding value; otherwise, replace it with "?". There are no nested brackets in s.

Solution: Hash Table and String Traversal

This problem can be efficiently solved using a hash table (or dictionary) to store the key-value pairs from knowledge and then traversing the input string s.

Algorithm:

1. Create a Hash Table: Build a hash table (dictionary in Python) mapping keys to their values from the knowledge array. This allows for O(1) lookup time for keys.

2. Iterate Through the String: Iterate through the input string s.

3. Handle Bracket Pairs: When an opening parenthesis '(' is encountered:

   • Find the corresponding closing parenthesis ')'.
   • Extract the key enclosed within the parentheses.
   • Look up the key in the hash table.
   • If the key exists, replace the bracket pair in the output string with its value.
   • If the key does not exist, replace the bracket pair with "?".

4. Handle Other Characters: If a character is not an opening parenthesis, append it directly to the output string.

5. Return the Result: After processing the entire string, return the constructed output string.

Time Complexity: O(m + n), where m is the length of s and n is the length of knowledge. The hash table creation takes O(n), and string traversal takes O(m).

Space Complexity: O(n), the space used by the hash table to store knowledge. The space used for the output string is also considered, but it's proportional to the input string's length.

Code Implementation (Python)

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        knowledge_map = {}
        for key, value in knowledge:
            knowledge_map[key] = value
 
        result = ""
        i = 0
        while i < len(s):
            if s[i] == '(':
                j = s.find(')', i)
                key = s[i+1:j]
                result += knowledge_map.get(key, "?")
                i = j + 1
            else:
                result += s[i]
                i += 1
        return result

Code Implementation (Java)

import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> knowledgeMap = new HashMap<>();
        for (List<String> entry : knowledge) {
            knowledgeMap.put(entry.get(0), entry.get(1));
        }
 
        StringBuilder result = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '(') {
                int j = s.indexOf(')', i);
                String key = s.substring(i + 1, j);
                result.append(knowledgeMap.getOrDefault(key, "?"));
                i = j + 1;
            } else {
                result.append(s.charAt(i));
                i++;
            }
        }
        return result.toString();
    }
}

(Other language implementations would follow a similar structure, using their respective hash table and string manipulation methods.)

The provided solutions in other languages (Java, C++, Go, TypeScript, Rust) follow the same algorithmic approach, adapting the data structures and syntax to their specific language features. They all achieve the same time and space complexity.