每日一题：LeetCode-394. 字符串解码

作者：半亩房顶

2023-12-19
北京
本文字数：1395 字
阅读完需：约 5 分钟

刷题使我快乐，满脸开心.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 <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
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()}