We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Evaluate the Bracket Pairs of a String

Difficulty: Medium

Problem Description

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key. You know the values of a wide range of keys, represented by a 2D string array knowledge. Your task is to evaluate all the bracket pairs in the string. Replace each bracket pair with its corresponding value from the knowledge array or with a question mark "?" if the value is unknown. Return the resulting string after evaluating all bracket pairs.

Key Insights

  • The string will contain bracket pairs with keys that need to be replaced.
  • A mapping of keys to values is provided through a 2D array.
  • If a key is not found in the mapping, it should be replaced by a question mark.
  • There are no nested brackets, simplifying the parsing of the string.
  • Each key appears at most once in the knowledge.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Each character is processed once. Space Complexity: O(k), where k is the number of key-value pairs in the knowledge array, due to the hash map storing the mappings.

Solution

To solve this problem, we can use a hash map (or dictionary) to store the key-value pairs from the knowledge array for quick lookup. Then, we can iterate through the string s, and whenever we encounter an opening bracket '(', we will capture the key until we find the corresponding closing bracket ')'. We will then replace the key with its value from the hash map if it exists, or with '?' if it does not. The result will be built using a list to optimize string concatenation.

Code Solutions

def evaluate_bracket_pairs(s, knowledge):
    # Create a dictionary to store key-value pairs from knowledge
    knowledge_dict = {key: value for key, value in knowledge}
    result = []
    i = 0

    while i < len(s):
        if s[i] == '(':
            # Start of a key
            j = i + 1
            while j < len(s) and s[j] != ')':
                j += 1
            key = s[i + 1:j]  # Extract the key
            # Replace the key with its value or '?' if not found
            result.append(knowledge_dict.get(key, '?'))
            i = j + 1  # Move past the closing bracket
        else:
            # Normal character, add to result
            result.append(s[i])
            i += 1

    return ''.join(result)
← Back to All Questions