題目出處
1807. Evaluate the Bracket Pairs of a String
難度
medium
題目分類
Array, Hash Table, String
2026-09-28 一刷
個人範例程式碼 - 一刷 (2026/09/28)
class Solution:
def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
table = {}
for k, v in knowledge:
table[k] = v
ans = []
start = -1
for i, c in enumerate(s):
if c == '(':
start = i+1 # skip ( and start collecting
elif c == ')':
key = s[start:i] # skip )
ans.append(table.get(key, "?"))
start = -1 # finish collecting
else:
if start == -1: # not collecting
ans.append(c)
return "".join(ans)
算法說明
建立一個查表，然後掃過原始字串，替換為表內有存在的值（找不到就是 ?）
- 建表
- 掃過 s，抓出 （）的片段，看有沒有在表內。
- 輸出結果
細節：也可以用 ans = "" 直接相加，
但字串是 immutable，每次 += 其實是建一條新字串再把舊內容複製過去，最壞情況會累積成 O(n^2)。
list 是 mutable，append 沒有複製過程，保持 O(1)，最後透過「 “".join() 」一次組好，總共 O(n)。
（CPython 對 += 有優化，但實測常看不出差別，但這不是語言保證，所以習慣上還是推薦用 list + join 避免潛在問題。）
Time Complexity
O(n+k) # n 是掃過字串的時間，K 是掃過 Knowledge 的時間 （不確定哪個大，這樣表示更清楚，知道哪個大後也能再簡化）
Space Complexity
O(n)