字符串解码(LC394)变体:额外处理 '|' 字符
哪些公司问过
答案要点
- 格式含义:[m|S] 表示 S 重复 m 次,可嵌套;先和面试官确认竖线的语义
- 双栈法:左括号时压入当前串,读数字到竖线后压入次数;右括号时弹出并拼接 prev + cur×k
- 递归解法:遇左括号进入递归,读次数、跳过竖线、解析内容到匹配的右括号后重复返回
- 复杂度 O(输出长度),栈深度等于嵌套层数;用 StringBuilder 等可变串减少拷贝
易错点
- 把竖线当普通字符拼进结果
- 只处理一位数字,次数大于 9 时出错
- 右括号时拼接顺序写反成 cur + prev
- 用不可变字符串反复相加,产生大量拷贝
面试官常见追问
- 和原题 LC394 写法上有什么不同?
- 解码结果非常长怎么办?
- 怎么校验输入是否合法?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场