Abstract / Summary

Given a string with nested brackets and values, compute the sum inside matching brackets according to their nesting levels.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method evaluate. The method receives a string s that may contain placeholders wrapped in parentheses and a list knowledge that maps placeholder keys to their replacement values. The goal is to produce a new string where each placeholder is substituted with its corresponding value from knowledge, or with a question mark (?) when the key is absent. The algorithm proceeds in a single pass over the input string, maintaining a small amount of state to distinguish between ordinary characters and characters that belong to a placeholder.

Key Steps

The first important operation is the construction of a fast-lookup structure from the knowledge list. By converting the list of pairs into a dictionary, the code enables O(1) retrieval of replacement values.

lookup = { key: value for key, value in knowledge }

The main loop iterates over each character c in the input string s. A boolean flag inside indicates whether the current position is inside a pair of parentheses. When an opening parenthesis is encountered, the flag is set to True and the temporary buffer key is cleared to start collecting the placeholder name.

if c == "(":
    inside = True
    key = ""
    continue

When a closing parenthesis is found, the flag is reset to False. The accumulated key is then used to query the lookup dictionary. If the key exists, its associated value is appended to the result; otherwise, a question mark is appended.

if c == ")":
    inside = False
    result += lookup.get(key, "?")
    continue

If the current character is not a parenthesis, the code decides where to place it based on the inside flag. Characters that belong to a placeholder are concatenated onto key; all other characters are directly appended to the output string.

if inside:
    key += c
else:
    result += c

After processing all characters, the method returns the assembled result.

Edge Cases Handled

The algorithm gracefully handles an empty input string because the loop simply does not execute and the initial empty result is returned. When knowledge is empty, the dictionary comprehension yields an empty dictionary, causing every placeholder lookup to fall back to the default "?". Missing keys are therefore represented by a question mark without raising an exception. The code also correctly processes consecutive placeholders, such as "()(())", because the inside flag is toggled precisely at each opening and closing parenthesis, ensuring that each pair is treated independently. Nested parentheses are not part of the problem specification, and the implementation treats the first closing parenthesis it encounters as the end of the current placeholder, which aligns with the expected flat placeholder format. Leading or trailing parentheses are handled in the same way; an unmatched opening parenthesis would keep inside true until the end of the string, causing any subsequent characters to be collected as part of a key, and the final result would reflect the lookup (or "?") when a closing parenthesis finally appears.

Performance Optimizations

The most noticeable optimization is the creation of the lookup dictionary using a dictionary comprehension. This transforms the list of key-value pairs into a hash table, allowing constant-time access for each placeholder substitution. The single-pass design eliminates the need for multiple scans of the input string, reducing overall processing time. By using a boolean flag and a small string buffer for the current key, the algorithm avoids more heavyweight data structures such as stacks or queues. Direct string concatenation (result += ...) is employed inside the loop; while Python strings are immutable, the interpreter optimizes repeated concatenations in CPython for short strings, and the approach keeps the code concise without sacrificing noticeable performance for typical input sizes. The use of dict.get with a default value eliminates an explicit conditional check for key existence, streamlining the substitution step.

Imagine a little machine that has a long string of beads, where some beads are tucked away inside small secret pockets marked by parentheses. The goal is to open these pockets, see what is hidden inside, and replace the secret code with a special prize that matches it.

First, the machine looks at a list of notes that tells it which secret code belongs to which prize. It saves these notes in a very clever way so it can find the answers super fast whenever it needs them.

Then, the machine walks down the line of beads one by one. If it sees an opening pocket, it starts listening for the secret code. While it is inside the pocket, it collects all the little letters to build the full secret word. Once it hits the closing pocket, it stops collecting and looks at its list of notes to see if it knows which prize that code stands for. If it knows the prize, it puts the prize down. If it does not find the code on its list, it adds a question mark instead to show it is puzzled.

If the machine is not currently inside a secret pocket, it just picks up the regular beads as they are and adds them to a growing chain. By the time it finishes looking at every single bead, it has built a brand new chain filled with the prizes gathered from those secret pockets.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++			Java
	leetcode.ca	C++	Python		Java		Go	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality