LeetCode 题解工作台
字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string] ，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，…
3
题型
3
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
class Solution: def decodeString(self, s: str) -> str:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
示例 1：
输入：s = "3[a]2[bc]" 输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]" 输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"
提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
解题思路
方法一
class Solution:
def decodeString(self, s: str) -> str:
s1, s2 = [], []
num, res = 0, ''
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == '[':
s1.append(num)
s2.append(res)
num, res = 0, ''
elif c == ']':
res = s2.pop() + res * s1.pop()
else:
res += c
return res
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * maxK) where maxK is the maximum repeat count, as each character can be processed multiple times. Space complexity is O(n) for stack usage in the iterative solution or recursion call stack in the recursive solution. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect the candidate to recognize nested repetition requires a stack or recursion.
- question_mark
Watch for mismanagement of multiple-digit repeat counts or nested brackets.
- question_mark
Look for concise handling of string concatenation to avoid repeated O(n^2) operations.
常见陷阱
外企场景- error
Confusing digits inside the encoded string with repeat counts, leading to incorrect expansion.
- error
Not correctly combining the previous string with repeated segments after popping from the stack.
- error
Failing to handle multiple nested brackets or multi-digit repeat numbers properly.
进阶变体
外企场景- arrow_right_alt
Allowing digits in the encoded string itself, requiring different parsing logic.
- arrow_right_alt
Limiting the maximum depth of nested brackets to test iterative versus recursive solutions.
- arrow_right_alt
Encoding with different delimiters or adding optional separators inside repeats.