力扣394——字符串解码

这道题主要涉及的是对递归和栈的理解。

原题

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

1
2
3

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

原题url：https://leetcode-cn.com/problems/decode-string/

解题

递归

这道题目，简单来看就是根据数字和内容，进行不断重复输出，最终得出结果。因此，递归也是最容易让人想到的。

数字代表内容需要重复的次数，[代表一次新的递归开始，]代表本次递归的结束，有点类似括号匹配这种问题。只是需要记录中间结果，以及最开始的s进过一次递归遍历后的下标位置。

基于上面的讲解，我们也就能够写出代码：

class Solution {
    public String decodeString(String s) {
        StringBuilder resultSb = new StringBuilder();
        dfs(s, 0, resultSb);
        return resultSb.toString();
    }

    public int dfs(String s, int index, StringBuilder resultSb) {
        // 需要重复的次数
        int count = 0;
        while (index < s.length()) {
            char temp = s.charAt(index);
            // 如果是数字，则先累计进count中
            if (temp >= '0' && temp <= '9') {
                count = count * 10 + temp - '0';
            }
            // 遇到'['，则开始新一轮的递归
            else if (temp == '[') {
                StringBuilder tempResult = new StringBuilder();
                index = dfs(s, index + 1, tempResult);
                // 重复
                for (int i = 0; i < count; i++) {
                    resultSb.append(tempResult);
                }
                // count进行重置
                count = 0;
            }
            // 遇到']'，结束递归
            else if (temp == ']') {
                            // 返回新的下标
                return index;
            }
            // 遇到字母
            else {
                resultSb.append(temp);
            }

            index++;
        }

        return index;
    }
}

提交OK。

利用栈

既然有递归的写法，那么自然有不递归的写法，这就需要借助栈了。大家可以类比成计算一段普通的数学表达式，里面有括号、数字、符号运算等，所以需要两个栈，分别存储数字和运算符。

这道题目自然也是需要两个栈的，一个用来存储重复的次数，一个用来存储中间的字符串结果。判断出栈、入栈的依据，依据是[]，[代表数字和字符串都压入相应的栈，]代表需要将数字和字符串都需要从栈首压出，进行计算。

接下来看看代码：

class Solution {
    public String decodeString(String s) {
        // 存放次数的栈
        Stack<Integer> countStack = new Stack<>();
        // 存放字符串的栈
        Stack<StringBuilder> sbStack = new Stack<>();
        // 临时存储字符串的内容
        StringBuilder tempSb = new StringBuilder();
        // 临时存储数字的内容
        int tempCount = 0;

        // 遍历
        for(char temp : s.toCharArray()) {
            // 如果是数字，则先累计进tempCount中
            if (temp >= '0' && temp <= '9') {
                tempCount = tempCount * 10 + temp - '0';
            }
            // 遇到'['，将之前的数字和字符串放进countStack中
            else if (temp == '[') {
                countStack.push(tempCount);
                tempCount = 0;

                sbStack.push(tempSb);
                tempSb = new StringBuilder();
            }
            // 遇到']'，从countStack拿出数字
            else if (temp == ']') {
                // 重复
                StringBuilder tempResult = new StringBuilder();
                int count = countStack.pop();
                for (int j = 0; j < count; j++) {
                    tempResult.append(tempSb);
                }
                // 拿出sbStack第一个
                StringBuilder sb = sbStack.pop();
                tempSb = sb.append(tempResult);
            }
            // 遇到字母
            else {
                tempSb.append(temp);
            }
        }
        
        return tempSb.toString();
    }
}