题目重点:两篇 VO 面经提最深深度字符串;先明确括号类型、输出边界和同深度并列,再给单次扫描方案。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版接受 ()、[]、{} 且严格成对嵌套;返回最大嵌套深度的一对括号内部内容,不含外层括号。
- 同深度有多段时返回最早闭合的一段;若题目要求所有段或最深字符而非整段,需改输出契约。
解题路线
- 从左到右遇左括号,将括号种类和索引压栈;右括号检查栈顶类型,不匹配即报非法输入。
- 闭合时以闭合前的栈深为该对括号深度,若更深则记录 s[open+1:close];若相等按训练版保留先前结果。
- 扫描结束仍有未闭合括号亦报错;文本与转义括号是否算语法要事先澄清。
- 若要返回所有最深文本,维护列表;若只要纯字符层,须决定嵌套括号内文本是否全部归属父层。
手动走一遍
训练串 a(b[c]d){e[f]} 中 [c] 和 [f] 都在第 2 层;若按最早闭合取结果,则返回 c。题目未明确这个示例或并列规定。
规模与取舍
扫描 O(n) 时间、栈最坏 O(n) 空间;在 Python 中反复切片比较内容可能增加复制成本,可先保存下标最后一次截取。
易错点与追问
容易失分的边界
- 只用计数器而不校验括号种类。
- 在弹栈之后才读取深度,差一层。
- 未确认同深度多段的返回格式。
- 未确认非法括号如何处理。
继续深挖
- 如果返回所有同深度段怎么办?
- 引号内括号是否忽略?
- 流式输入跨 chunk 怎样保持栈状态?
