Given an encoded string, return its 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].

Example：

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

解释下题目：

具体形式就是一个数字N加一个中括号，然后输出N次中括号里面的内容，其本质就是数学表达式求解的问题啦。

1. 堆栈

实际耗时：1ms

public String decodeString(String s) {
    LinkedList<String> stack = new LinkedList<>();
    int num = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') {
            num = num * 10 + c - '0';
        } else {
            if (num > 0) {
                stack.push(String.valueOf(num));
                num = 0;
            }
            if (c >= 'a' && c <= 'z') {
                stack.push(String.valueOf(c));
            } else if (c >= 'A' && c <= 'Z') {
                stack.push(String.valueOf(c));
            } else {
                // can only be '[' or ']'
                if (c == '[') {
                    stack.push(String.valueOf(c));
                } else {
                    // need to pop
                    StringBuilder tmp = new StringBuilder();
                    while (!stack.isEmpty()) {
                        String temp = stack.pop();
                        if (temp.equals("[")) {
                            break;
                        } else {
                            tmp.insert(0, temp);
                        }
                    }
                    String count = stack.pop();
                    stack.push(helper(count, tmp.toString()));
                }
            }
        }
    }
    StringBuilder res = new StringBuilder();
    while (!stack.isEmpty()) {
        res.append(stack.getLast());
        stack.removeLast();
    }
    return res.toString();
}

private String helper(String count, String s) {
    StringBuilder sb = new StringBuilder();
    try {
        for (int i = 0; i < Integer.valueOf(count); i++) {
            sb.append(s);
        }
    } catch (NumberFormatException c) {
        System.out.println(count);
    }

    return sb.toString();
}

踩过的坑：emmm其实是包含大小写的....我一开始以为只有小写，但是无伤大雅。

  思路与求数学表达式的值的思路一模一样。

时间复杂度O(n)

空间复杂度O(n)