刷题使我快乐，满脸开心.jpg
- 来源：力扣（LeetCode）
- 链接：https://leetcode.cn/problems/decode-string/
- 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 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]
思路
这道题我第一反应是递归，栈方法也可以的，只是这里只说我自己写的递归了~
对于数字+括号的组合，我觉得反倒是没什么大问题，因为这里递归的进出条件都很清晰
问题就复杂在了字母 和 数字+括号的组合的杂揉处理上了
我的思路就是，先试着拆分问题：
- 对于
数字+括号可以较快的写出来一套逻辑，可以把这部分看做一个整体 - 对于
字母，如果把括号、数字考虑进来会很复杂，所以就只考虑纯字母的一段作为一个整体
如此拆分之后，在这两种组合之间，还需要考虑的就是
- 如何处理嵌套中的
纯字母的整体 - 如何将各个
整体组合起来
第一个问题其实好解决，那就是将需要处理嵌套内容时，深入一层递归去处理，这样就是要么内部是一个整体，要么内部还有新的递归。也因此，右括号]要作为递归的一个退出条件
第二个问题，有点难想，可以转化下这个问题，那就是
如何处理每个
整体后的字符串
这样想可能会有些启发作用，就是可以在每个整体的尾部再调用一次递归函数。这样，新的函数要么到边界满足这个退出条件、要么发现了下一个整体继续处理，这样就可以将各个整体串联起来了。
至此，上代码
代码
func decodeString(s string) string {
i := 0
sBytes := []byte(s)
n := len(sBytes)
var getStr func() string
getStr = func() string {
// i == n 为总体退出条件
// 右括号为数字+嵌套循环组合的退出条件
if i == n || sBytes[i] == ']' {
return ""
}
temp := ""
// 数字+嵌套循环组合 作为一个整体
if sBytes[i]-'0' <= 9 {
num := 0
for sBytes[i]-'0' <= 9 {
num = num*10 + int(sBytes[i]-'0')
i++
}
// 跳过左括号
i++
loopStr := getStr()
// 跳过右括号
i++
for ; num > 0; num-- {
temp += loopStr
}
} else {
// 一段纯字母作为一个整体
for i < n && sBytes[i] >= 'a' && sBytes[i] <= 'z' {
temp += string(sBytes[i])
i++
}
}
// 后续继续获取，主要根据尾字母和下标做限制
return temp + getStr()
}
return getStr()
}