Evaluate the Bracket Pairs of a String — LeetCode 1807 Python Solution

The problem

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

Example

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

Python solution

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        d = {a: b for a, b in knowledge}
        i, n = 0, len(s)
        ans = []
        while i < n:
            if s[i] == '(':
                j = s.find(')', i + 1)
                ans.append(d.get(s[i + 1 : j], '?'))
                i = j
            else:
                ans.append(s[i])
            i += 1
        return ''.join(ans)

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1807. Evaluate the Bracket Pairs of a String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems