题目描述
思路解析
一句话答案：LeetCode 1807 替换字符串中的括号内容：先把 knowledge 建成哈希表，再从左到右扫一遍 s，括号外字母照抄、括号内的键查表替换、查不到换问号，一趟拼出结果，时间 O(n+m)。
括号里的键换成值，拼出完整结果串
给一个字符串 s，只有小写字母和成对、不嵌套的小括号，每对括号里是一个非空的键。另给清单 knowledge，每项是「键，值」。要把 s 里每对括号连同键换成对应的值，查不到的键整对换成一个问号，括号外的字母原样保留。题面 s = "(name)is(age)yearsold"，name 对应 bob、age 对应 two，得到 "bobistwoyearsold"。
每查一个键都翻遍清单，慢在哪
不建表的话，收出括号里的键后，就得到 knowledge 里从头找哪项的键和它一样。可 s 里可能有很多对括号，每对都把清单从头翻一遍。设 s 长 n、清单键值总字符数是 m，括号对数最多到 n 量级、每次线性找又是 m 量级，乘起来接近 n 乘 m，键一多、清单一长就拖慢。症结在「按键找值」每回都白翻，翻一次记下就够。
先建一张表，把查键做成一步到位
把 knowledge 一次性搬进哈希表，也就是按键直接拿到值的那种表。表建好后不论查多少次键都是常数时间，不必再回原清单里翻。
剩下的事是从左到右把 s 扫一遍：遇到括号外的字母直接抄进结果；遇到左括号，就从下一个字符起把键一个个收起来，直到撞见右括号，再拿整段键去表里查——查到就把这对括号换成对应的值，查不到就换一个问号。一趟扫完，结果串就拼好了。
指针为什么一趟扫到底，不用回头
括号不嵌套、每个左括号都配一个右括号，这两条保证扫描不必回头。参考代码里下标 i 从头走到末尾：s 当前位不是左括号就把字母接进结果；是左括号就用 find 找到配对的右括号位置 j，把两括号之间那段当键去查表、把查到的接进结果，再让 i 直接跳到 j 后接着走。每段括号一次处理完、指针不倒退，整趟就是线性的。收键要把括号里整段收全再查，只取头一个字符会把多字符的键查错。
(name)is(age)yearsold 扫到最后拼成什么
先建表，记下 name 对应 bob、age 对应 two。指针从下标 0 出发：先撞上左括号，收键收到 name，到右括号闭合，查表得 bob，结果是 "bob"。接着 i、s 两个字母在括号外，原样抄上成 "bobis"。再遇左括号，收键 age，查表得 two，拼成 "bobistwo"。最后 yearsold 全在括号外逐个抄进去，得到 "bobistwoyearsold"。若换成 s = "hi(name)"、清单里查不到 name，这对括号就换成问号、hi 原样保留，结果是 "hi?"。
两段都线性，剩几个坑要防
建表把 knowledge 的 m 个字符过一遍，扫描把 s 的 n 个字符过一遍，查表平均常数时间，相加是 O(n+m)。空间上哈希表存下所有键值是 O(m)、拼结果的容器和输出等长是 O(n)，峰值取两者之和 O(n+m)，不是常数。
查不到的键必须换成一个问号，留空会漏字符、保留原键会把括号或键名混进结果。括号外的字母只能原样抄，别也拿去查表，像 (a)(a)aaa 里括号中的 a 要换值、后面裸着的三个 a 得原样留着。同一个键出现几次就各查各换，别只换第一次。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套动作:先建表,再一遍扫。括号外的字母照抄,括号内的字符拼成键去查表,查到用值替换、查不到用问号替换。下面每一帧都在套这个流程,先看建表,再看指针一格一格往右走。
概览 · 括号内外：先看清这串 "z(a)(a)(bc)" 的结构。开头的 z 在括号外,是要原样保留的普通字母;后面是三对括号,里面的键分别是 a、a、bc。绿色标出的是括号内的键、灰色是括号本身。心里有了这张地图,再开始建表和扫描。
建表 · 空表：正式扫描前,先把 knowledge 这张清单搬进哈希表。现在表还空着,一条都没有。建表的好处是,后面不管查多少次键,每次都是常数时间,不用每次都在原始清单里从头找一遍。
建表 · 加入 a：knowledge 的第一条是键 a 对应值 go,放进表里。以后只要在括号里读到键 a,一查表就能拿到 go。
建表 · 加入 k：第二条是键 k 对应值 hi,也放进表里。注意这条 k 在待处理的字符串里其实一次都用不上,但表里存着不碍事,查不到才是问题,查得到用不到没关系。
建表完成 · 准备扫描：表建好了,一共两条。现在把指针放回字符串开头,准备从下标 0 开始一格一格往右扫。结果串目前是空的,接下来会一点点拼出来。
下标 0 · 抄字母 "z"：指针在下标 0,这是括号外面的普通字母 "z"。不用查表,直接原样抄进结果。结果串现在是 "z"。
下标 1 · 左括号：指针走到下标 1,这是一个左括号。看到左括号就知道:接下来一段是括号里的键。先把键的缓冲清空,从下一格开始一个字符一个字符地把键收进来,直到撞见右括号为止。
下标 2 · 键收进 "a"：指针在括号里,读到字符 "a",把它接到键的缓冲上,现在收集到的键是 "a"。还没到右括号,继续往右收,看键会不会更长。
下标 3 · 键 "a" 查表：指针走到下标 3 的右括号,这对括号闭合了。中间收集到的键是 "a"。现在拿这个键去知识表里查一下,看看表里有没有这一行。
下标 3 · 命中 → "go"：表里正好有键 "a" 这一行,对应的值是 "go"。于是把左括号、键、右括号这一整对,统统换成 "go" 接到结果后面。现在结果串变成 "zgo"。
下标 4 · 左括号：指针走到下标 4,这是一个左括号。看到左括号就知道:接下来一段是括号里的键。先把键的缓冲清空,从下一格开始一个字符一个字符地把键收进来,直到撞见右括号为止。
下标 5 · 键收进 "a"：指针在括号里,读到字符 "a",把它接到键的缓冲上,现在收集到的键是 "a"。还没到右括号,继续往右收,看键会不会更长。
下标 6 · 键 "a" 查表：指针走到下标 6 的右括号,这对括号闭合了。中间收集到的键是 "a"。现在拿这个键去知识表里查一下,看看表里有没有这一行。
下标 6 · 命中 → "go"：表里正好有键 "a" 这一行,对应的值是 "go"。于是把左括号、键、右括号这一整对,统统换成 "go" 接到结果后面。现在结果串变成 "zgogo"。
下标 7 · 左括号：指针走到下标 7,这是一个左括号。看到左括号就知道:接下来一段是括号里的键。先把键的缓冲清空,从下一格开始一个字符一个字符地把键收进来,直到撞见右括号为止。
下标 8 · 键收进 "b"：指针在括号里,读到字符 "b",把它接到键的缓冲上,现在收集到的键是 "b"。还没到右括号,继续往右收,看键会不会更长。
下标 9 · 键收进 "c"：指针在括号里,读到字符 "c",把它接到键的缓冲上,现在收集到的键是 "bc"。还没到右括号,继续往右收,看键会不会更长。
下标 10 · 键 "bc" 查表：指针走到下标 10 的右括号,这对括号闭合了。中间收集到的键是 "bc"。现在拿这个键去知识表里查一下,看看表里有没有这一行。
下标 10 · 查不到 → "?"：拿这个键到哈希表里查一次,发现没有 "bc" 这个键。按规则,查不到的键要用一个问号来替换,而不是留空或保留原样。于是这对括号换成 "?" 接到结果后面,结果串变成 "zgogo?"。
扫描完成：指针走到字符串末尾,整个 s 只扫了一遍,每个字符都处理过了。括号外的字母原样抄,括号内的键查表替换,结果串一路拼到现在是 "zgogo?"。
回放 · 答案 "zgogo?"：回放一遍怎么拼出来的:开头的 z 在括号外,原样保留;第一对 (a) 查到 go、第二对 (a) 同一个键还是查到 go,同一个键出现两次都替换;最后 (bc) 在表里查不到,换成一个问号。连起来正好是 "zgogo?"。
对照验证：最后对照一下规则有没有走偏:括号外的字母原样保留、括号内的键查到就用值替换、查不到就用一个问号替换,同一个键出现几次就替换几次。演示这三种情况都碰上了,答案 "zgogo?" 完全符合规则。
边界先想清:没有括号就整串原样抄;键查不到就换一个问号;同一个键重复出现每次都换,而括号外的相同字母原样不动。
面试重点:括号不嵌套所以一遍线性扫就够;知识表用哈希表把查值做成常数时间,比在清单里线性找快;若改成允许嵌套,要用栈或递归从内层往外层求值。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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)复杂度
- 时间：O(n + m)，n 是 s 的长度,m 是 knowledge 里所有键和值的总字符数。建表把 m 个字符过一遍;扫描时每个字符只经过常数次(找右括号是不重叠地往后走,整趟合起来仍是 O(n)),查表平均常数时间。两段相加是 O(n + m)
- 空间：O(n + m)，峰值占用两块:哈希表存下所有键值,是 O(m);拼结果的容器最终和输出等长,是 O(n)。两者都随输入变大而变大,峰值取二者之和 O(n + m),不是常数
易错点
面试追问把动画讲成自己的话
追问为什么一遍扫描就够,不用反复回头?
追问知识表为什么用哈希表,直接在原始清单里线性找不行吗?
追问如果题目改成允许嵌套括号,思路要怎么调整?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
查找用户活跃分钟数
LeetCode 1817 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题