#1807

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Evaluate the Bracket Pairs of a String

Quickly evaluate a string with bracketed keys using array scanning and hash table lookups for efficient replacements.

Problem Statement

You are given a string s containing lowercase letters and bracket pairs. Each bracket pair contains a non-empty key, and you are provided with a knowledge array mapping keys to values. Replace each key in the bracket pairs with its corresponding value from knowledge. If a key is not present, replace it with a '?'.

For example, given s = "(name)is(age)yearsold" and knowledge = [["name","bob"],["age","two"]], you should evaluate the string to produce "bobistwoyearsold". Repeated keys must be replaced consistently, and characters outside brackets remain unchanged. No nested brackets exist.

Examples

Example 1

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]

Output: "bobistwoyearsold"

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

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"

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.

Solution Approach

Hash Lookup Preparation

Convert the knowledge array into a hash map for O(1) key lookups. This allows each bracket key to be quickly replaced without repeatedly scanning the knowledge list.

Single Pass Array Scan

Iterate through the string character by character, detecting bracket pairs. Extract the key between '(' and ')', then replace it with its value from the hash map or '?' if unknown. Append all non-bracket characters directly to the result.

Handle Repeated Keys Efficiently

Because keys can appear multiple times, processing in a single pass ensures all occurrences are replaced consistently. Avoid rescanning the string or knowledge array for each occurrence to maintain linear time performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k) where n is the length of s and k is the number of knowledge entries, due to the single scan and hash table lookup. Space complexity is O(k + n) for the hash map and the resulting string construction.

What Interviewers Usually Probe

Check for missing keys and replace them with '?' consistently.
Repeated keys can appear multiple times; ask how to handle duplicates efficiently.
Brackets are guaranteed to be non-nested, simplifying linear scanning.

Common Pitfalls or Variants

Common pitfalls

Forgetting to replace unknown keys with '?' instead of leaving brackets intact.
Rescanning the knowledge array for each bracket instead of using a hash map.
Not handling multiple occurrences of the same key correctly.

Follow-up variants

Evaluate strings where brackets may contain multi-character keys or numbers.
Process strings with larger knowledge sets requiring optimized hash map construction.
Handle cases where keys appear consecutively or interleaved with non-bracket characters.

FAQ

How do I handle unknown keys in Evaluate the Bracket Pairs of a String?

Any key not present in the knowledge array should be replaced with a '?' to indicate an unknown value.

Can keys in bracket pairs repeat?

Yes, keys may appear multiple times. Each occurrence must be replaced using the hash map lookup without rescanning the knowledge array.

Are nested brackets possible?

No, every open '(' has a corresponding closing ')', and no brackets are nested, simplifying linear evaluation.

What is the best pattern for replacing keys in this problem?

Use array scanning combined with hash lookups. Process the string once and replace keys on-the-fly for optimal performance.

Does GhostInterview help with repeated keys?

Yes, it automatically handles repeated keys consistently using the hash map approach and flags unknown keys with '?'.

terminal

Solution

Solution 1: Hash Table + Simulation

First, we use a hash table $d$ to record the key-value pairs in `knowledge`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)

Continue Practicing

#1684 count the number of consistent strings #1948 delete duplicate folders in system #1980 find unique binary string