第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0394. 字符串解码

题目地址(394. 字符串解码)

题目描述

1
给定一个经过编码的字符串,返回它解码后的字符串。
2
3
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
4
5
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
6
7
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
8
9
10
11
示例 1:
12
13
输入:s = "3[a]2[bc]"
14
输出:"aaabcbc"
15
示例 2:
16
17
输入:s = "3[a2[c]]"
18
输出:"accaccacc"
19
示例 3:
20
21
输入:s = "2[abc]3[cd]ef"
22
输出:"abcabccdcdcdef"
23
示例 4:
24
25
输入:s = "abc3[cd]xyz"
26
输出:"abccdcdcdxyz"
Copied!

前置知识

  • 括号匹配

使用栈

思路

题目要求将一个经过编码的字符解码并返回解码后的字符串。题目给定的条件是只有四种可能出现的字符
  1. 1.
    字母
  2. 2.
    数字
  3. 3.
    [
  4. 4.
    ]
并且输入的方括号总是满足要求的(成对出现),数字只表示重复次数。
那么根据以上条件,可以看出其括号符合栈先进后出的特性以及递归的特质,稍后我们使用递归来解。
那么现在看一下迭代的解法。
我们可以利用 stack 来实现这个操作,遍历这个字符串 s,判断每一个字符的类型:
  • 如果是字母 --> 添加到 stack 当中
  • 如果是数字 --> 先不着急添加到 stack 中 --> 因为有可能有多位
  • 如果是 [ --> 说明重复字符串开始 --> 将数字入栈 --> 并且将数字清零
  • 如果是 ] --> 说明重复字符串结束 --> 将重复字符串重复前一步储存的数字遍
拿题目给的例子s = "3[a2[c]]" 来说:
在遇到 之前,我们不断执行压栈操作:
当遇到 的时候,说明我们应该出栈了,不断出栈知道对应的,这中间的就是 repeatStr。
但是要重复几次呢? 我们需要继续出栈,直到非数字为止,这个数字我们记录为 repeatCount。
而最终的字符串就是 repeatCount 个 repeatStr 拼接的形式。 并将其看成一个字母压入栈中
继续,后面的逻辑是一样的:
(最终图)

代码

代码支持:Python
Python:
1
class Solution:
2
def decodeString(self, s: str) -> str:
3
stack = []
4
for c in s:
5
if c == ']':
6
repeatStr = ''
7
repeatCount = ''
8
while stack and stack[-1] != '[':
9
repeatStr = stack.pop() + repeatStr
10
# pop 掉 "["
11
stack.pop()
12
while stack and stack[-1].isnumeric():
13
repeatCount = stack.pop() + repeatCount
14
stack.append(repeatStr * int(repeatCount))
15
else:
16
stack.append(c)
17
return "".join(stack)
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为解码后的 s 的长度。
  • 空间复杂度:$O(N)$,其中 N 为解码后的 s 的长度。

递归

思路

递归的解法也是类似。由于递归的解法并不比迭代书写简单,以及递归我们将在第三节讲述。
主逻辑仍然和迭代一样。 只不过每次碰到左括号就进入递归,碰到右括号就跳出递归返回即可。
唯一需要注意的是,我这里使用了 start 指针跟踪当前遍历到的位置, 因此如果使用递归需要在递归返回后更新指针。

代码

1
class Solution:
2
3
def decodeString(self, s: str) -> str:
4
def dfs(start):
5
repeat_str = repeat_count = ''
6
while start < len(s):
7
if s[start].isnumeric():
8
repeat_count += s[start]
9
elif s[start] == '[':
10
# 更新指针
11
start, t_str = dfs(start + 1)
12
# repeat_count 仅作用于 t_str,而不作用于当前的 repeat_str
13
repeat_str = repeat_str + t_str * int(repeat_count)
14
repeat_count = ''
15
elif s[start] == ']':
16
return start, repeat_str
17
else:
18
repeat_str += s[start]
19
start += 1
20
return repeat_str
21
return dfs(0)
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为解码后的 s 的长度。
  • 空间复杂度:$O(N)$,其中 N 为解码后的 s 的长度。
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解