LeetCode 394 字符串解码

Ciel Yang 收录于类别练习 OJ解题报告

2021-01-26 2021-01-26 约 1437 字预计阅读 3 分钟

本题是一道典型的递归面试题，同时又常被用来考察非递归解法，即栈的使用，应当仔细观察两种解法的异同，体会递归的特点。

题目描述

原题链接如下： LeetCode 394 字符串解码

题目大意

假设一个只含有字母的字符串已通过特殊的方式编码，即把重复的子串使用 n[s] 的形式表示，n 表示子串 s 的重复次数（其中 n 大于 1），求解码之后的字符串。

输入与输出

示例输入为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Input 1:
s = "3[a]2[bc]"

Input 2:
s = "3[a2[c]]"

Input 3:
s = "2[abc]3[cd]ef"

Input 4:
s = "abc3[cd]xyz"

对应输出为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Outout 1:
"aaabcbc"

Output 2:
"accaccacc"

Output 3:
"abcabccdcdcdef"

Output 4:
"abccdcdcdxyz"

解题思路

编码后的字符串可能出现括号嵌套的情况，比如 "ab3[c2[de]f]g" 这样的输入，显然可以使用递归方法由内向外“剥洋葱”，同时也可以使用迭代方法替代递归。

解法一：递归

核心思路是：在我们扫描字符串内容时，一旦遇到 [] 包裹的内容就表明我们需要先把内部内容处理完毕，然后按照 [ 前的数字重复填入结果容器。大体步骤如下：

构造空的容器以存放解码后的内容
检查字符串的字符：
- 如果遇到数字，则直到遇到 [ 为止之后的字符必定都是数字，需要暂存
- 遇到 [ 则表明需要递归解码子串：
  1. 即递归进入步骤 1
  2. 获取递归结果，即子串的解码内容
  3. 结合已有的数字（必定存在），重复在容器中填入子串解码内容
- 遇到 ] 表明当前的子串解码中止，即刻返回子串解码结果
- 遇到普通字符则直接放入容器中

这个方法的关键在于，一旦遇到 [ 我们就会进入递归处理子串，而后不断层层深入，直到最内层的子串出现 ]，就会返回其解码结果。这样就能保证 [] 的正确匹配，而且不必关心如何匹配。

解法二：栈

迭代法处理递归程序显然要使用栈进行辅助，即用栈不断缓存 [ 之前的内容，然后根据子串解码结果不断出栈进行组装。本题的特殊之处在于一般情况下，我们要把数字和字符分类处理，需要用到两个栈，那么就必须正确匹配两个栈的内容。

先考虑处理形式为 前部字符串 + 中部数字 + [后部字符串] 的简单编码串（如 "a2[b]"），我们会暂存 a 和 2，然后解码 [b] 代表的子串，之后进行合并，即 a2[b] = a + (2 * b)。那么，在处理复杂的字符串时，也可依照相似的思路，大体步骤如下：

建立空的容器，暂时容纳子串解码内容，同时建立空的字符串栈和数字栈
遍历字符串中的字符：
- 遇到数字，则代表之后的字符直到 [ 都是数字，把它们转换为数字 num
- 遇到 [ 则准备进入子串的解码：
  1. 把 num 暂存到数字栈中
  2. 把容器内容存入字符串栈
  3. 清空容器
- 遇到 ] 则代表子串解码完成：
  1. 把数字栈中的数字栈顶弹出（必定存在）
  2. 容器内容重复次数就是数字栈顶
  3. 字符串栈和上一步得到的字符串合并，作为新的容器内容

这样，直到编码字符串遍历完成，容器中保存的就是正确的解码内容。

这个办法的核心思路是保证字符串栈存放前部字符串，数字栈中存放中部数字，容器中存放后部字符串解码内容，即字符串栈和数字栈匹配，每次子串解码完成就需要重新组装前、中、后内容作为新的后部内容。

注意："3[a]" 形式的字符串前部为空，但是也要把空字符串存入字符串栈中，保证两个栈的匹配不出现错误。

代码

递归法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {

    private var idx = 0

    fun decodeString(s: String): String {
        return decodeHelper(s)
    }

    private fun decodeHelper(s: String): String {
        val re = StringBuilder()
        var num = 0
        while (idx < s.length) {
            when (val c = s[idx]) {
                in '0'..'9' -> num = num * 10 + (c - '0')
                '[' -> {
                    idx++
                    val inner = decodeHelper(s)
                    repeat(num) { re.append(inner) }
                    num = 0
                }
                ']' -> {
                    return re.toString()
                }
                else -> re.append(c)
            }
            idx++
        }
        return re.toString()
    }
}

迭代法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

    fun decodeString(s: String): String {
        val nums = ArrayDeque<Int>()
        val strs = ArrayDeque<String>()
        val re = StringBuilder()
        var num = 0
        for (c in s) {
            when (c) {
                in '0'..'9' -> num = num * 10 + (c - '0')
                '[' -> {
                    nums.addLast(num)
                    strs.addLast(re.toString())
                    re.clear()
                    num = 0
                }
                ']' -> {
                    val cnt = nums.removeLast()
                    val temp = re.repeat(cnt)
                    re.clear()
                    re.append(strs.removeLast())
                    re.append(temp)
                }
                else -> re.append(c)
            }
        }
        return re.toString()
    }
}

目录