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:

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

思路

利用堆栈来访问括号里面的各个元素。

用到了几种常用的类: List, Stack, StringBuffer/StringBuilder, Character, Integer

其中，定义一个list可以直接用Arrays.asList方法，就不用list.add方法了，比较简洁。

需要注意的是，一开始没有考虑到数字会有多位，如”100[abc]”，这是之后才加的。

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
31
32
33
34
35
36
37
38
39
public class Solution {
    public String decodeString(String s) {
        StringBuffer res = new StringBuffer();
        List<String> nums = Arrays.asList("0","1","2","3","4","5","6","7","8","9");
        Stack<String> p = new Stack<String>();
        int i = 0;
        int length = s.length();
        while(i < length){
            String cur = Character.toString(s.charAt(i));
            if (!cur.equals("]")){
                p.push(cur);
            }
            else{
                StringBuffer tmp = new StringBuffer();
                while(!p.peek().equals("[")){
                    tmp.append(p.pop());
                }
                StringBuffer tmp_num = new StringBuffer();
                p.pop();
                while(!p.empty() && nums.contains(p.peek())){
                    tmp_num.append(p.pop());
                }
                int times = Integer.parseInt(tmp_num.reverse().toString());
                for (int k = 0; k < times; k++){
                    p.push(tmp.toString());
                }
            }
            i++;
        }
        while(!p.empty()){
            res.append(p.pop());
        }
        return res.reverse().toString();
    }
}