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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Evaluate the Bracket Pairs of a String

Number: 1934

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a string s containing some bracket pairs that enclose keys, and a list of key-value pairs in the knowledge array, replace every bracket pair in s with its corresponding value from knowledge. If a key does not have a corresponding value in knowledge, then replace the bracket pair with a question mark. Note that the keys inside the brackets are non-empty and there is no nested bracket pair.

Key Insights

  • Use a hash table (or dictionary) to store the key-value mappings from the knowledge array for efficient lookup.
  • Traverse the input string s using a pointer; when encountering an open bracket, extract the key between '(' and ')'.
  • Replace the entire bracket pair with the mapped value if it exists, otherwise replace it with '?'.
  • Since there is no nesting, the extraction of keys is straightforward and can be done in one pass.

Space and Time Complexity

Time Complexity: O(n + k) where n is the length of s and k is the total number of characters in the keys. Since each key extraction and lookup is done in constant time on average, the overall time complexity is linear. Space Complexity: O(m) where m is the number of key-value pairs stored in the hash table.

Solution

The solution first converts the knowledge array into a dictionary for O(1) lookups. Then, it iterates through each character in s and uses a pointer to detect bracket pairs. When an open bracket is found, it collects characters until the closing bracket is reached to form the key. The key is then looked up in the dictionary; if found, its corresponding value is appended to the result string, otherwise a '?' is appended. This approach ensures that each character in s is processed once, providing an efficient and straightforward solution.

Code Solutions

# Python solution using a dictionary and a pointer-based scan

def evaluate(s: str, knowledge: list[list[str]]) -> str:
    # Create a dictionary from knowledge for efficient lookup
    mapping = {key: value for key, value in knowledge}
    
    result = []  # Using list for accumulating result characters
    i = 0
    
    # Iterate through the string
    while i < len(s):
        if s[i] == '(':
            # Start of a bracket pair found, extract key
            i += 1  # Move past '('
            key_start = i
            # Find the closing bracket
            while s[i] != ')':
                i += 1
            key = s[key_start:i]  # Extract the key between the brackets
            # Append corresponding value or '?' if key not in mapping
            result.append(mapping.get(key, "?"))
            i += 1  # Move past ')'
        else:
            # Append regular character
            result.append(s[i])
            i += 1
            
    return "".join(result)

# Example usage:
# s = "(name)is(age)yearsold"
# knowledge = [["name","bob"], ["age","two"]]
# print(evaluate(s, knowledge))
← Back to All Questions