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".

Recursion

递归的做法总是最直接, 最好想到的方法. 字符串有两种可能:

  1. k[encoded_string].
  2. encoded_string. 当k == 1的时候. 可忽略k.

所以我们要分别处理这两种情况, k[encoded_string] 中的 encoded_string 可以做为一个规模略小的子问题处理.

代码如下: 

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
public String decodeString(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); ) {
        int j = i;
        if (Character.isDigit(s.charAt(i))) {
            // parse the number before []
            for (; j < s.length() && Character.isDigit(s.charAt(j)); j++) ;
            int n = Integer.parseInt(s.substring(i, j));
            // get the string inside []
            int start = ++j;
            int flag = 1;
            for (; j < s.length() && flag != 0; j++) {
                if (s.charAt(j) == '[') {
                    flag++;
                } else if (s.charAt(j) == ']') {
                    flag--;
                }
            }
            String sub = decodeString(s.substring(start, j - 1));
            // append n times of the substring
            for (int k = 0; k < n; k++) {
                sb.append(sub);
            }
        } else {
            // there is no number in the begining of the string
            // get the string before the next number.
            for (; j < s.length() && !Character.isDigit(s.charAt(j)); j++) ;
            sb.append(s.substring(i, j));
        }
        i = j;
    }
    return sb.toString();
}

Stack

能用递归解的问题, 一般都能转化为Stack.

没有自己写, 论坛上找的代码. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String decodeString(String s) {
    Stack<Integer> intStack = new Stack<>();
    Stack<StringBuilder> strStack = new Stack<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for (char ch : s.toCharArray()) {
        if (Character.isDigit(ch)) {
            k = k * 10 + ch - '0';
        } else if (ch == '[') {
            intStack.push(k);
            strStack.push(cur);
            cur = new StringBuilder();
            k = 0;
        } else if (ch == ']') {
            StringBuilder tmp = cur;
            cur = strStack.pop();
            for (k = intStack.pop(); k > 0; --k) cur.append(tmp);
        } else cur.append(ch);
    }
    return cur.toString();
}

Ref: https://discuss.leetcode.com/topic/57159/simple-java-solution-using-stack