算法
LeetCode

LeetCode-394-字符串解码

# LeetCode-394-字符串解码

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

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

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

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

示例1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

1
2

示例2：

输入：s = "3[a2[c]]"
输出："accaccacc"

1
2

示例3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

1
2

示例4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

1
2

# 解题思路

方法1、栈：

观察示例可知，当出现括号时，需要考虑括号前的数字

由于有时候括号不止1个，而且括号内的字符也不止1组，所以需要2个栈(或者队列)来进行存储，此外还需要一个res存储最终拼接的字符串。

顺序进行遍历，情况分为以下4种：

0<=当前字符<=9时，记录当前num，num=c[i]-'0'，但是num可能不止一个数字，当字符为100时，下一个也是num，如果直接覆盖会导致数字丢失，于是num=num * 10 + c[i] - '0'正是考虑这种情况。
当前字符==[左括号时，记录括号前的num，并将num置0，方便下次记录。同时需要记录数字之前出现的所有英文字符，使用str的栈进行先前结果的存储，strStack.push(res.toString());，复用res准备记录括号内的英文字符。
当前字符是a-z或者A-Z范围内时，直接进行字符串拼接res.append(c[i])
当前字符==]右括号时，需要将括号内的字符重复，同时需要将之前保存的字符串和括号内的字符串进行拼接。首先弹出数字栈内的数字tempNum，利用一个临时的字符串tempStr保存之前的结果，从字符栈中弹出之前的字符串strStack.pop()，并转为StringBuilder类型赋值给tempStr，循环添加到tempStr中，此时的res保存的是括号内的字符，循环次数为tempNum。进行玩括号内字符添加后，将临时字符串赋值给res，继续进行循环判断。

最后，返回res.toString()

# Java代码

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        char[] c = s.toCharArray();
        int num = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] >= '0' && c[i] <= '9') {
                num = num * 10 + c[i] - '0';
            } else if (c[i] == '[') {
                numStack.push(num);
                num = 0;
                strStack.push(res.toString());
                res = new StringBuilder();
            } else if (('a' <= c[i] && c[i] <= 'z') || ('A' <= c[i] && c[i] <= 'Z')) {
                res.append(c[i]);
            } else if (c[i] == ']') {
                int tempNum = numStack.pop();
                StringBuilder tempStr = new StringBuilder(strStack.pop());
                for (int j = 0; j < tempNum; j++) {
                    tempStr.append(res);
                }
                res = tempStr;
            }
        }
        return res.toString();
    }
}