Leetcode 394-字符串解码

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

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

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

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

题解

辅助栈法

一、一个栈存储数字，一个存储字符串

二、从左到右遍历每个字符，分四种情况：

1.数字
对于数字，要注意题目条件：s 中所有整数的取值范围为 [1, 300] ，也就是数字有可能是不止一位的，数字结束的标志是遇到[
2.左括号[
遍历到左括号，我们让当前字符串curString和当前数字curNum分别入自己的栈。
同时让它们回归初始值""和0
3.右括号]
遍历到右括号，那就可以进行解码操作了。
具体而言，就是弹出数字栈的元素，作为要循环的次数num，弹出字符串栈的元素tmp，在tmp后面拼接num个curString
最后将curString置为tmp
4.字符
如果是字符，直接拼接在当前字符串后面

三、返回值

curString

class Solution {
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();

        String curString="";
        int cuNum=0;
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            //1.c是数字
            //要考虑数字为两位数或者三位数的情况
            if(c<='9'&&c>='0') cuNum=cuNum*10+c-'0';
            //2.c是左括号
            //此时将curString和curNum都入栈
            else if(c=='['){
                numStack.push(cuNum);
                strStack.push(curString);
                cuNum=0;
                curString="";
            } 
            //3.c是右括号
            //开始计算
            else if(c==']'){
                int num=numStack.pop();
                String tmp=strStack.pop();
                //注意这块是>0而不是>=0
                while(num>0){
                    tmp+=curString;
                    num--;
                }
                curString=tmp;
            }else{//此时c为字符
                curString+=c;
            }
        }
        return curString;
    }
}