1807. Evaluate the Bracket Pairs of a String

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}

2. 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.

3. 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]

4. 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, '?'))

5. Update the index i to move past the closing bracket.

6. 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])

7. Increment i to continue to the next character.

8. 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.

9. 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.

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.

Solution Implementation

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).

Learn more about how to find time and space complexity quickly using problem constraints.