题目描述
思路解析动画文字版
记住这套动作:先建表,再一遍扫。括号外的字母照抄,括号内的字符拼成键去查表,查到用值替换、查不到用问号替换。下面每一帧都在套这个流程,先看建表,再看指针一格一格往右走。
概览 · 括号内外：先看清这串 "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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题