1807. Evaluate the Bracket Pairs of a String

MediumArrayHash TableString
Leetcode Link

Problem Description

This problem involves a string s which contains several bracket pairs. Each pair encapsulates a key. For instance, in this string: "(name)is(age)yearsold", there are two pairs of brackets with the keys "name" and "age".

There is also a 2D array called knowledge that holds pairs of keys and their corresponding values, such as [["name","Alice"], ["age","12"]]. This array tells us what value each key holds.

The task is to parse through the string s and replace each key within the brackets with its corresponding value from the knowledge array. If a key is not found in knowledge, it should be replaced with a question mark "?".

Every key will be unique and present just once in the knowledge base. The string s does not contain any nested brackets, simplifying the parsing process.

The goal is to return a new string with all bracket pairs evaluated and substituted by their corresponding values or a "?" if the key's value is unknown.

Intuition

The intuition behind the solution is to perform a linear scan of the string s, using a variable i to keep track of our position. We proceed through the string character by character until we encounter an opening bracket (.

When an opening bracket is detected, we know that a key is started. We then find the closing bracket ) that pairs with the opening bracket. The substring within the brackets is the key we are interested in.

We check the dictionary d we've made from the knowledge array to see if the key exists:

  • If the key has a corresponding value in d, we add that value to the result string.
  • If the key does not exist in d, we append a question mark ? to the result string.

Once we have replaced the key with its value or a question mark, we move i to the position just after the closing bracket since all characters within the brackets have been processed.

If we encounter any character other than an opening bracket, we simply add that character to the result string, as it does not need any substitution.

Our process continues until we've scanned all characters within the string s. In the end, we join all parts of our result list into a single string and return it as the solution.

The operation of finding the closing bracket can be done efficiently using the find() method in Python, and accessing dictionary values with the get() method allows us the option of providing a default value if the key does not exist.

Solution Approach

The solution leverages a dictionary and simple string traversal to effectively solve the problem. The approach follows these steps:

  1. Convert the knowledge list of lists into a dictionary where each key-value pair is one key from the bracket pairs and its corresponding value. This allows for constant-time access to the values while we traverse the string s.
1d = {a: b for a, b in knowledge}
  1. Initialize an index i to start at the first character of the string s and a ans list to hold the parts of the new string we're building.

  2. Start iterating over the string s using i. We need to check each character and decide what to do:

    • If the current character is an opening bracket '(', we must find the matching closing bracket ')' to identify the key within.
    • We use the find() method to locate the index j of the closing bracket.
    • Obtain the key by slicing the string s from i + 1 to j to get the content within brackets.
1j = s.find(')', i + 1)
2key = s[i + 1 : j]
  1. Use the key to look up the value in the dictionary d. If the key is found, append the value to the ans list; otherwise, append a question mark '?'.
1ans.append(d.get(key, '?'))
  1. Update the index i to move past the closing bracket.

  2. If the current character isn't an opening bracket, append it directly to the ans list because it's part of the final string.

1ans.append(s[i])
  1. Increment i to continue to the next character.

  2. After the while loop completes, we will have iterated over the entire string, replacing all bracketed keys with their corresponding values or a question mark.

  3. Finally, join the elements of the ans list into a string:

1return ''.join(ans)

No advanced algorithms are needed for this problem; it primarily relies on string manipulation techniques and dictionary usage. The approach is efficient as it makes one pass through the string and accesses the dictionary values in constant time.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's go through an example to illustrate the solution approach. Suppose we have the following string s and knowledge base:

s = "Hi, my name is (name) and I am (age) years old." knowledge = [["name","Bob"], ["age","25"]]

First, we convert the knowledge list into a dictionary, d:

d = {"name": "Bob", "age": "25"}

Now, we initialize our starting index i = 0, and an empty list ans = [] to store parts of our new string.

We begin iterating over the string s. The first characters "Hi, my name is " are not within brackets, so we add them directly to ans.

At index 14, we encounter an opening bracket (. Now we need to find the corresponding closing bracket ):

  • We use s.find(')', i + 1) and find the closing bracket at index 19.
  • The key within the brackets is s[i + 1 : j], which yields "name".
  • We search for "name" in d and find that it corresponds to the value "Bob".
  • ans.append(d.get(key, '?')) will result in appending "Bob" to ans.

Next, we update i to be just past the closing bracket; i = 20.

Continuing to iterate, we add the characters " and I am " directly to ans, as they are outside of brackets.

Upon reaching the next opening bracket at index 29, we repeat the process:

  • We find the closing bracket at index 33.
  • We identify the key as "age".
  • We search for "age" and obtain the value "25" from d.
  • We append "25" to ans.

Finally, i is updated to index 34, and we add the remaining characters " years old." to ans.

After processing the entire string, we join all parts of ans using ''.join(ans) to get the final string:

"Hi, my name is Bob and I am 25 years old."

This is the string with the keys in the original string s replaced by their corresponding values from the knowledge base, which is the desired outcome. If at any point a key had not been found in d, a '?' would have been appended instead.

Python Solution

1class Solution:
2    def evaluate(self, expression: str, knowledge: List[List[str]]) -> str:
3        # Convert the 'knowledge' list of lists into a dictionary for fast lookups
4        knowledge_dict = {key: value for key, value in knowledge}
5      
6        index, length_of_expression = 0, len(expression)
7        result = []  # This list will collect the pieces of the evaluated expression
8      
9        # Iterate through the expression string
10        while index < length_of_expression:
11            # If the current character is '(', find the corresponding ')'
12            if expression[index] == '(':
13                closing_paren_index = expression.find(')', index + 1)
14                # Extract the key between the parentheses
15                key = expression[index + 1 : closing_paren_index]
16                # Append the value from the knowledge dictionary if it exists, otherwise '?'
17                result.append(knowledge_dict.get(key, '?'))
18                # Move the index past the closing parenthesis
19                index = closing_paren_index
20            else:
21                # Append the current character to the result if it's not part of a key
22                result.append(expression[index])
23            # Move to the next character
24            index += 1
25      
26        # Join all parts of the result list into a single string
27        return ''.join(result)
28

Java Solution

1class Solution {
2  
3    public String evaluate(String s, List<List<String>> knowledge) {
4      
5        // Create a dictionary from the provided knowledge list
6        Map<String, String> dictionary = new HashMap<>(knowledge.size());
7        // Populate the dictionary with key-value pairs from the knowledge list
8        for (List<String> entry : knowledge) {
9            dictionary.put(entry.get(0), entry.get(1));
10        }
11      
12        // StringBuilder to construct the final evaluated string
13        StringBuilder evaluatedString = new StringBuilder();
14      
15        // Iterate over the entire input string character by character
16        for (int i = 0; i < s.length(); ++i) {
17          
18            // If current character is '(', it's the start of a key
19            if (s.charAt(i) == '(') {
20              
21                // Find the corresponding closing ')' to get the key
22                int j = s.indexOf(')', i + 1);
23              
24                // Extract the key from the input string
25                String key = s.substring(i + 1, j);
26              
27                // Append the value for the key from the dictionary to the result
28                // If the key is not found, append "?"
29                evaluatedString.append(dictionary.getOrDefault(key, "?"));
30              
31                // Move the index to the character after the closing ')'
32                i = j;
33            } else {
34                // If current character is not '(', append it directly to the result
35                evaluatedString.append(s.charAt(i));
36            }
37        }
38      
39        // Return the fully evaluated string
40        return evaluatedString.toString();
41    }
42}
43

C++ Solution

1#include <string>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7    // Function that takes a string s and a knowledge base as input, and replaces
8    // all substrings enclosed in parentheses with their corresponding values from
9    // the knowledge base. If a substring does not exist in the knowledge base,
10    // it replaces it with '?'.
11    string evaluate(string s, vector<vector<string>>& knowledge) {
12        // Creating a dictionary (hash map) to store the key-value pairs
13        // from the knowledge base for quick lookup.
14        unordered_map<string, string> knowledgeMap;
15        for (auto& entry : knowledge) {
16            knowledgeMap[entry[0]] = entry[1];
17        }
18
19        // String to store the final result after all replacements are done.
20        string result;
21        // Iterating over the input string to find and replace values.
22        for (int i = 0; i < s.size(); ++i) {
23            if (s[i] == '(') { // Check if the current character is an opening parenthesis.
24                int j = s.find(")", i + 1); // Find the corresponding closing parenthesis.
25                // Extract the key between the parentheses.
26                string key = s.substr(i + 1, j - i - 1);
27                // Lookup the key in the knowledge map and append to result;
28                // if key not found, append '?'.
29                result += knowledgeMap.count(key) ? knowledgeMap[key] : "?";
30                i = j; // Move the index to the position of the closing parenthesis.
31            } else {
32                // Append the current character to result if it's not an opening parenthesis.
33                result += s[i];
34            }
35        }
36        return result; // Return the final result string.
37    }
38};
39

Typescript Solution

1function evaluate(expression: string, knowledgePairs: string[][]): string {
2    // Get the length of the expression.
3    const expressionLength = expression.length;
4    // Create a map to hold the knowledge key-value pairs.
5    const knowledgeMap = new Map<string, string>();
6    // Populate the map using the knowledgePairs array.
7    for (const [key, value] of knowledgePairs) {
8        knowledgeMap.set(key, value);
9    }
10    // Initialize an array to hold the parts of the answer as we process the expression.
11    const answerParts = [];
12    // Initialize the index to iterate through the expression.
13    let index = 0;
14  
15    // Iterate over the characters in the expression.
16    while (index < expressionLength) {
17        // Check if the current character is the beginning of a key placeholder.
18        if (expression[index] === '(') {
19            // Find the closing parenthesis for the current key placeholder.
20            const closingIndex = expression.indexOf(')', index + 1);
21            // Extract the key from inside the parenthesis.
22            const key = expression.slice(index + 1, closingIndex);
23            // Retrieve the value associated with the key from the map, defaulting to '?'.
24            const value = knowledgeMap.get(key) ?? '?';
25            // Add the value to the answerParts array.
26            answerParts.push(value);
27            // Move the index to the position after the closing parenthesis.
28            index = closingIndex;
29        } else {
30            // If the current character is not a parenthesis, add it to the answerParts array as is.
31            answerParts.push(expression[index]);
32        }
33        // Move to the next character.
34        index++;
35    }
36  
37    // Join all parts of the answer to form the final string and return it.
38    return answerParts.join('');
39}
40

Time and Space Complexity

The time complexity of the code is O(n + k), where n is the length of the string s and k is the total number of characters in all keys of the dictionary d. Here's the breakdown:

  • We loop through the entire string s once, which gives us O(n).
  • Constructing the dictionary d has a time complexity of O(k), assuming a constant time complexity for each insert operation into the hash table, and k is the total length of all keys present in knowledge.

The space complexity of the code is O(m + n), where m is the space required to store the dictionary d and n is the space for the answer string (assuming each character can be counted as taking O(1) space):

  • The dictionary d will have a space complexity of O(m), where m is the sum of the lengths of all keys and values in the knowledge list.
  • The list ans that accumulates the answer will have at most the same length as the input string s, since each character in s is processed once, leading to O(n) space.

Therefore, the overall space complexity is the sum of the space complexities of d and ans, i.e., O(m + n).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫