Introduction

In this blog post, we will explore how to solve the LeetCode problem "1807" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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] = [keyi, valuei] indicates that key keyi has a value of valuei. You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key keyi, you will: Replace keyi and the bracket pair with the key's corresponding valuei. If you do not know the value of the key, you will replace keyi 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 <= 105 0 <= knowledge.length <= 105 knowledge[i].length == 2 1 <= keyi.length, valuei.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. keyi and valuei consist of lowercase English letters. Each keyi in knowledge is unique.

Explanation

Here's the solution:

• High-level approach:

  • Create a dictionary (hash map) to store the key-value pairs from the knowledge array for fast lookups.
  • Iterate through the input string s, identifying bracket pairs.
  • For each bracket pair, extract the key, look up its value in the dictionary, and replace the pair with the corresponding value or "?" if not found.

• Complexity:

  • Runtime Complexity: O(n + k), where n is the length of the string s and k is the number of key-value pairs in the knowledge array.
  • Storage Complexity: O(k), where k is the number of key-value pairs in the knowledge array (for storing the dictionary).

Code

    def evaluate(s: str, knowledge: list[list[str]]) -> str:
    """
    Evaluates bracket pairs in a string based on provided knowledge.

    Args:
        s: The input string with bracket pairs.
        knowledge: A list of key-value pairs.

    Returns:
        The resulting string after evaluating the bracket pairs.
    """

    knowledge_dict = {key: value for key, value in knowledge}
    result = ""
    i = 0
    while i < len(s):
        if s[i] == '(':
            j = i + 1
            while j < len(s) and s[j] != ')':
                j += 1
            key = s[i + 1:j]
            if key in knowledge_dict:
                result += knowledge_dict[key]
            else:
                result += "?"
            i = j + 1
        else:
            result += s[i]
            i += 1

    return result