1. 字符串解码问题概述遇到394.字符串解码这类问题时我们通常需要处理包含数字和字母的特殊编码字符串。这类问题在真实开发场景中非常常见比如处理API返回的压缩数据、解析配置文件中的嵌套结构或是处理某些特定格式的日志文件。典型输入示例3[a]2[bc] → aaabcbc3[a2[c]] → accaccacc2[abc]3[cd]ef → abcabccdcdcdef2. 问题核心难点解析2.1 嵌套结构处理当遇到类似3[a2[c]]的多层嵌套时需要先处理最内层的解码。这就像拆俄罗斯套娃必须从最里面的娃娃开始拆解。2.2 数字与字符的混合处理数字可能不止一位如10[ab]需要完整读取数字部分。在实际操作中我建议使用while循环来累积数字位while s[i].isdigit(): num num * 10 int(s[i]) i 12.3 边界条件处理需要特别注意几种特殊情况纯字母字符串如abc空字符串只有数字没有字母如3[]数字为0的情况如0[a]3. 两种经典解法对比3.1 递归解法递归解法思路直观适合嵌套层级不深的情况。核心在于遇到[时递归处理子串遇到]时返回当前结果。递归解法模板def decodeString(s): def helper(i): res while i len(s) and s[i] ! ]: if not s[i].isdigit(): res s[i] i 1 else: num 0 while s[i].isdigit(): num num * 10 int(s[i]) i 1 i 1 # skip [ sub, i helper(i) res sub * num return res, i 1 return helper(0)[0]3.2 栈解法栈解法更适合处理深度嵌套的情况也是面试中最常考察的解法。核心思路是使用两个栈分别存储数字和字符串片段。栈解法实现步骤初始化数字栈num_stack和字符串栈str_stack遍历字符串遇到数字累积计算完整数字遇到[将当前res和num分别压栈然后重置遇到]弹出数字和字符串进行拼接遇到字母直接追加到当前res完整实现代码def decodeString(s): stack [] curr_num 0 curr_str for char in s: if char.isdigit(): curr_num curr_num * 10 int(char) elif char [: stack.append((curr_str, curr_num)) curr_str curr_num 0 elif char ]: prev_str, num stack.pop() curr_str prev_str curr_str * num else: curr_str char return curr_str4. 性能优化与边界处理4.1 时间复杂度分析两种解法的时间复杂度都是O(n)其中n是解码后字符串的长度。这是因为每个字符最多被处理常数次。4.2 空间复杂度对比递归解法O(m)调用栈空间m是最大嵌套深度栈解法O(m)栈空间但实际使用中通常比递归更节省内存4.3 特殊输入处理建议在实际工程应用中建议增加以下校验括号匹配检查数字后必须跟[的校验空字符串处理非法字符过滤5. 实际应用场景扩展5.1 配置文件解析许多配置文件使用类似的编码方式存储重复内容。例如server { location /api { limit_req 10[req/s]; } }5.2 数据压缩传输在带宽受限的场景下重复字符串常用这种编码压缩。比如100[0]比000...0(100个0)更节省空间。5.3 日志处理系统日志中经常出现的重复错误信息可以使用这种编码优化存储。例如3[Error: connection timeout]2[Warning: high CPU usage]6. 常见错误与调试技巧6.1 数字累积错误常见错误是忘记重置curr_num或在数字转换时出错。调试时可以打印中间变量print(fProcessing {char}, curr_num{curr_num}, curr_str{curr_str})6.2 栈操作顺序错误特别注意压栈和弹栈的顺序必须对称。一个实用的调试技巧是可视化栈状态[栈顶] (, 3) (a, 2) [栈底]6.3 边界条件遗漏建议编写测试用例时特别考虑空输入无数字的纯字母嵌套超过3层的情况数字0的特殊情况7. 进阶挑战与变种问题7.1 支持转义字符如果需要支持类似3[a]b]的情况即允许]出现在非结尾位置需要引入转义字符处理逻辑。7.2 多分隔符支持扩展支持多种分隔符如3{a}2(b)需要修改判断条件。7.3 逆向编码问题实现将普通字符串编码为压缩格式的逆操作这在实际数据压缩中很有价值。8. 工程实践建议8.1 代码可读性优化建议将核心逻辑拆分为单独方法并添加详细注释def _parse_number(s, index): 解析从index开始的数字部分 num 0 while index len(s) and s[index].isdigit(): num num * 10 int(s[index]) index 1 return num, index8.2 单元测试编写完善的测试用例应该包含test_cases [ (3[a]2[bc], aaabcbc), (3[a2[c]], accaccacc), (2[abc]3[cd]ef, abcabccdcdcdef), (10[a], a*10), (, ), (abc, abc), ]8.3 性能监控对于大规模数据处理建议添加性能统计import time start time.perf_counter() result decodeString(large_input) elapsed time.perf_counter() - start print(fDecoded {len(result)} chars in {elapsed:.2f}s)9. 不同语言实现差异9.1 Java实现特点Java中字符串不可变使用StringBuilder更高效StringBuilder res new StringBuilder(); // ... while(num-- 0) { res.append(tempStr); }9.2 JavaScript实现注意JS中数字转换要注意NaN检查let num 0; while(!isNaN(parseInt(s[i]))) { num num * 10 parseInt(s[i]); }9.3 Go语言实现Go需要特别注意字符串的rune处理for i, r : range s { switch { case r 0 r 9: num num*10 int(r-0) // ... } }10. 算法选择建议对于不同场景我建议面试场景优先使用栈解法更容易解释且不易出错工程场景如果确定嵌套不深递归代码更简洁性能敏感场景可以考虑迭代手动栈的实现最后分享一个调试技巧在复杂嵌套情况下可以给每个递归层级添加缩进打印直观观察处理过程def helper(i, indent0): print( *indent fEnter helper({i})) # ... print( *indent fExit helper({i}): {res}) return res, i
)
