Evaluate the Bracket Pairs of a String

Medium

Asked by:

9 views

Topics:

StringsArrays

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [key_i, value_i] indicates that key key_i has a value of value_i.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key key_i, you will:

Replace key_i and the bracket pair with the key's corresponding value_i.
If you do not know the value of the key, you will replace key_i and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

Constraints:

1 <= s.length <= 10⁵
0 <= knowledge.length <= 10⁵
knowledge[i].length == 2
1 <= key_i.length, value_i.length <= 10
s consists of lowercase English letters and round brackets '(' and ')'.
Every open bracket '(' in s will have a corresponding close bracket ')'.
The key in each bracket pair of s will be non-empty.
There will not be any nested bracket pairs in s.
key_i and value_i consist of lowercase English letters.
Each key_i in knowledge is unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters can the string `s` contain besides bracket pairs and keys?
If a key in the string `s` does not exist in the `knowledge` list, what should I replace it with?
Can the bracket pairs be nested?
Can the knowledge list contain empty keys or values?
Is the order of keys in the knowledge list significant? If so, which value should I pick if there are duplicate keys?

Brute Force Solution

Approach

The brute force approach to this problem means trying out every possible combination. We'll go through each bracketed expression and try to find its value by looking through all the possible key-value pairs until we find the right one or determine that it's missing.

Here's how the algorithm would work step-by-step:

Go through the input string, one character at a time.
When you find an opening bracket, remember its location.
Keep going until you find the matching closing bracket.
Everything between the brackets is a key that we need to find a value for.
Look through every key-value pair provided.
If the key in the string matches a key in the pairs, replace the bracketed text with the corresponding value.
If the key doesn't match any of the provided keys, replace the bracketed text with a question mark.
Continue scanning the string to repeat the above process for any remaining bracket pairs.
Finally, put the resulting string together and return it.

Code Implementation

def evaluate_bracket_pairs_brute_force(input_string, knowledge): 
    result = ''
    i = 0
    while i < len(input_string):
        if input_string[i] == '(': 
            # Found an opening bracket, start extracting the key
            start_index = i + 1
            end_index = i + 1
            while end_index < len(input_string) and input_string[end_index] != ')':
                end_index += 1

            key = input_string[start_index:end_index]

            found_value = False
            for key_value_pair in knowledge:
                if key_value_pair[0] == key:
                    result += key_value_pair[1]
                    found_value = True
                    break

            # If no matching key is found, append '?'
            if not found_value:
                result += '?'

            i = end_index + 1
        else:
            result += input_string[i]
            i += 1

    return result

Big(O) Analysis

Time Complexity

O(n*m*k) – The outer loop iterates through the input string 's' of length 'n'. For each opening bracket found, an inner loop searches for the closing bracket, taking at most O(n) time in the worst case. Once the key is extracted (bracket contents), we iterate through the provided knowledge pairs. Assuming 'm' key-value pairs, this lookup takes O(m) time. Within the key-value pair, we need to compare the extracted key to keys of length 'k' in the knowledge pairs. Therefore, each check has the complexity of O(k). Combining these, the overall time complexity becomes O(n*m*k).

Space Complexity

O(M) – The described brute force approach primarily utilizes space for storing the key that is extracted from between the brackets. In the worst case, this key's length could be proportional to M, where M is the maximum length of a bracketed expression within the input string. The algorithm also iterates through the key-value pairs, but it doesn't store them; it just reads them one by one. No other significant auxiliary data structures are created, therefore the dominant space complexity is determined by the size of the longest key to be extracted for comparison, leading to O(M).

Optimal Solution

Approach

This problem involves substituting parts of a string enclosed in parentheses with values from a provided lookup table. The most efficient approach is to simply read through the original string once, checking for the parentheses along the way. This allows us to build the result in a single pass.

Here's how the algorithm would work step-by-step:

Start reading the main string from the beginning, one character at a time.
If you encounter an open parenthesis, this indicates a key you should look up.
Extract the key within the parentheses.
Use this key to find its corresponding value from the given key-value pairs.
Replace the entire parenthesized expression with its value.
If you do not find the key in the key-value pairs, replace the entire expression with a question mark.
If you encounter a regular character (not part of a parenthesized expression), just add it to your result.
Continue this process until you have read the entire string. You will have the fully evaluated string.

Code Implementation

def evaluate_bracket_pairs(input_string, knowledge_pairs):
    result = ""
    index = 0
    while index < len(input_string):
        if input_string[index] == '(': 
            # Found an open parenthesis, start extracting the key.
            index += 1
            key_start_index = index
            while index < len(input_string) and input_string[index] != ')':
                index += 1
            key = input_string[key_start_index:index]

            # Look up the key in the knowledge pairs.
            if key in knowledge_pairs:
                result += knowledge_pairs[key]
            else:
                result += "?"
        else:
            # Append the current character to the result.
            result += input_string[index]
        index += 1
    return result

Big(O) Analysis

Time Complexity

O(n + m) – The algorithm iterates through the input string 's' of length 'n' once. Inside the loop, when a key is encountered within parentheses, the algorithm looks up the key in the key-value pairs, which is a dictionary or hash map of size 'm'. The key lookup in a hash map takes O(1) time on average. Therefore, the overall time complexity is dominated by the linear scan of the input string and the constant-time lookups in the key-value pairs. In the worst case, every character is part of a key, so we have 'n' lookups. Considering both, the time complexity is O(n + m), where n is the length of the string and m is the size of the key-value pairs.

Space Complexity

O(M) – The auxiliary space is primarily determined by the size of the string that stores the result as we build it. In the worst case, where no substitutions occur, the result string could have the same length as the input string, or if substitutions make the string longer than the original string, it grows according to the size of the substituted values. We also need space to store the 'key' extracted between the parenthesis. Let M be the length of the resultant string, and in the worst case the size of the key inside parenthesis is dependent on the length of the input string, so the auxiliary space is O(M).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately as there's nothing to evaluate.
Null or empty knowledge dictionary	Treat all bracket pairs as unresolved, resulting in their removal from the output string.
Input string contains unbalanced brackets (e.g., only opening brackets)	Ignore any unmatched opening bracket and continue processing the rest of the string.
Nested bracket pairs (e.g., (a(b)c))	Handle only the outermost matching brackets, as the problem description only requests evaluation of bracket pairs, not nested structures.
Knowledge dictionary contains null or empty values	Treat null/empty values as valid substitutions, effectively replacing the bracketed key with an empty string.
Knowledge dictionary key doesn't exist	Replace the unresolved bracket pair with a question mark '?' as specified in the problem description.
Very long input string or large knowledge dictionary	Ensure the chosen approach (e.g., using StringBuilder and HashMap) scales efficiently to avoid performance bottlenecks.
Bracket keys containing special characters, including other brackets	The solution should correctly identify the keys based on the specified bracket delimiters and handle any internal special characters as part of the key.

Null or empty input string

How to Handle:

Return an empty string immediately as there's nothing to evaluate.

Null or empty knowledge dictionary

How to Handle:

Treat all bracket pairs as unresolved, resulting in their removal from the output string.

Input string contains unbalanced brackets (e.g., only opening brackets)

How to Handle:

Ignore any unmatched opening bracket and continue processing the rest of the string.

Nested bracket pairs (e.g., (a(b)c))

How to Handle:

Handle only the outermost matching brackets, as the problem description only requests evaluation of bracket pairs, not nested structures.

Knowledge dictionary contains null or empty values

How to Handle:

Treat null/empty values as valid substitutions, effectively replacing the bracketed key with an empty string.

Knowledge dictionary key doesn't exist

How to Handle:

Replace the unresolved bracket pair with a question mark '?' as specified in the problem description.

Very long input string or large knowledge dictionary

How to Handle:

Ensure the chosen approach (e.g., using StringBuilder and HashMap) scales efficiently to avoid performance bottlenecks.

Bracket keys containing special characters, including other brackets

How to Handle:

The solution should correctly identify the keys based on the specified bracket delimiters and handle any internal special characters as part of the key.