Problem

Given an expression s includes numbers, letters and brackets. 

Number represents the number of repetitions inside the brackets(can be a string or another expression)．

Please expand expression to be a string.


Example
s = abc3[a] return abcaaa
s = 3[abc] return abcabcabc
s = 4[ac]dy, return acacacacdy
s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz

思路

1. 当遇到字母的时候, sb不断添加
2. 当遇到数字的时候, 组合数字
3. 当遇到 '[' 的时候, 找到和它对应的 ']' 的位置, 递归处理该区间的string.
4. 所以需要传多两个参数代表区间

    public String expressionExpand(String s) {
        // 1. when char at current position is an alphabetic char, than add to the stringbuilder, and move on
        // 2. if char is number, record the number and move on. and the number might be multiple digits. 
        // 3. if char is '[', then find its corresponding ']', and then expand the subproblem
        StringBuilder sb =  new StringBuilder();
        expand(s, sb, 0, s.length() - 1);
        return sb.toString();
    }

    private void expand(String s, StringBuilder sb, int start, int end) {
        if (start > end) return;

        while (start <= end && Character.isLetter(s.charAt(start))) {
            sb.append(s.charAt(start));
            start++;
        } 
        int number = 0;
        while (start <= end && Character.isDigit(s.charAt(start))) {
            number = number * 10 + s.charAt(start) - '0';
            start++;
        }

        if  (start <= end && s.charAt(start) == '[') {
            int brackets = 1;
            int index = start + 1;
            while (brackets != 0 && index <= end) {
                if (s.charAt(index) == '[') brackets++;
                if (s.charAt(index) == ']') brackets--;
                index++;
            }
            for (int i = 0; i < number; i++) {
                expand(s, sb, start + 1, index - 2);    
            }
            expand(s, sb, index, end);
        }
    }

一点点优化

• 因为如果上面的number值太大的话, 那么递归次数便会很多了
• 因此改成有返回值
• 时间复杂度： O(n ^ 2), 因为每一层都需要遍历字符串找到最后一个“】”

    public String expressionExpand(String s) {
        return expand(s, 0, s.length() - 1);
    }
    private String expand(String s, int start, int end) {
        if (start > end) return "";

        StringBuilder sb = new StringBuilder();
        while (start <= end && Character.isLetter(s.charAt(start))) {
            sb.append(s.charAt(start));
            start++;
        } 
        int number = 0;
        while (start <= end && Character.isDigit(s.charAt(start))) {
            number = number * 10 + s.charAt(start) - '0';
            start++;
        }

        if  (start <= end && s.charAt(start) == '[') {
            int brackets = 1;
            int index = start + 1;
            while (brackets != 0 && index <= end) {
                if (s.charAt(index) == '[') brackets++;
                if (s.charAt(index) == ']') brackets--;
                index++;
            }
            String sub = expand(s, start + 1, index - 2);
            for (int i = 0; i < number; i++) {
                sb.append(sub);
            }
            sb.append(expand(s, index, end));
        }
        return sb.toString();
    }

简洁版

    public String decodeString(String s) {
        if (s == null || s.length() == 0) return "";
        StringBuilder sb = new StringBuilder();

        int number = 0;
        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);
            if (Character.isLetter(ch)) {
                sb.append(ch);
            } else if (Character.isDigit(ch)) {
                number = number * 10 + ch - '0';
            } else if (ch == '[') {
                int lc = 1;
                for (int j = i + 1; j < s.length(); j++) {
                    char c = s.charAt(j);
                    if (c == '[') lc++;
                    if (c == ']') lc--;
                    if (lc == 0) {
                        String sub = decodeString(s.substring(i + 1, j));
                        for (int k = 0; k < number; k++) 
                            sb.append(sub);
                        i = j;
                        number = 0;

                        break;
                    }
                }
            }
        }
        return sb.toString();
    }

优化

• 非递归，因为只需要遍历字符串一次， 所以时间复杂度是O(n)

    public String decodeString(String s) {
        if (s == null || s.length() == 0) return "";

        Stack<Object> stack = new Stack<>();

        int number = 0;
        StringBuilder sb = new StringBuilder();
        StringBuilder whole = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                number = number * 10 + ch - '0';
            } else if (ch == '[') {
                stack.push(number);
                number = 0;
            } else if (Character.isLetter(ch)) {
                stack.push(ch);
            } else {
                while (!stack.isEmpty()) {
                    if (stack.peek() instanceof Integer) {
                        int num = (int)stack.pop();
                        String sub = sb.toString();
                        for (int k = 1; k < num; k++)
                            sb.append(sub);
                        stack.push(sb.toString());
                        sb.setLength(0);
                        break;
                    } else {
                        sb.insert(0, stack.pop());    
                    }
                }
            }
        }
        while (!stack.isEmpty()) {
            whole.insert(0, stack.pop());
        }
        return whole.toString();
    }