https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string

Nothing very special about this problem, we need to traverse our string and deal with data inside brackets. Let us do it in the following way:

  1. Create d: dictionary of knowledge
  2. Split s into parts, using (. Imagine, that s = (name)is(age)yearsold, then splitted list will be ['', 'name)is', 'age)yearsold']. It will look like this: first part will not have closing bracket, and each next part will have closing bracket.
  3. So, we add t[0] to final solution and then for each next part we againg use split, now by “)” and check if we have first part in d or not: and either add ? to answer or corresponding value. Also we add second part b, which goes after brackets.

Complexity: time complexity is O(m + n), where m is the length of s and n is the total length of all the words in knowledge: we created dictionary once and then we do one split with O(n) and then for each part we do another split and total length of all parts is O(n). Space complexity is also O(m+n).

class Solution:
    def evaluate(self, s, knowledge):
        d = {k:v for k, v in knowledge}
        t = s.split("(")
        ans = t[0]
        for i in range(1, len(t)):
            a, b = t[i].split(")")
            ans += d.get(a, "?") + b
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 1807