394. Decode String

394. Decode String

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

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

My Solutions：

用两个stack，分别储存StringBuilder(用来组成字母）和数字。用一个StringBuilder res保存结果，用一个int num保存当前数字。

在依次检查input里的每一个char时，根据char做如下判断：

• 如果char是一个数字

  • 如果num是0，把之前的res存入string stack

  • 计算新的num值: num = 10 * num + c - '0'; 这一步的是为了算数字，比如32就是三十二

• 如果char是【，把之前存下来的数字存入数字stack中，重置num，重置res，因为将要有新的字母组合

• 如果char是一个字母，把字母append到res上

• 如果char是】，取出string stack里的stringbuilder top，取出int stack里的数字n。把res append到top上n次。给res赋值top

举个例子“3[a2[c]]”：

• 3：string stack里加入一个空的stringbuilder;num=3

• 【： int stack里加入3；num=0; res=new StringBuilder;

• a：res="a";

• 2：string stack里加入"a"; num = 2

• 【：int stack里加入2；num=0, res=new StringBuilder

• c：res="c";

• 】：top=“a”; n=2; res变成“acc”

• 】：top=""; n = 3; res变成“accaccacc”

class Solution {
    public String decodeString(String s) {
        Stack<Integer> counters = new Stack<>();
        Stack<StringBuilder> strings = new Stack<>();

        StringBuilder res = new StringBuilder();
        int num = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                if (num == 0) strings.push(res); //把之前的结果先存入string stack
                num = 10 * num + c - '0';
                
            } else if (c == '[') {
                counters.push(num); //把【之前的数字存入数字stack
                num = 0; //重置num
                res = new StringBuilder(); 
                
            } else if (Character.isLetter(c)) {
                res.append(c);
                
            } else if (c == ']') {
                StringBuilder top = strings.pop(); //top是之前存入在string stack里的char
                int n = counters.pop(); //n是此【】里需要循环的次数
                while (n-- != 0) top.append(res); //res是此【】里的char
                res = top;
            }
        }
        return res.toString();
    }
}