题解 | #字符串解码#

import java.util.*;

/**
 * NC199 字符串解码
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    public String decodeString (String s) {
        // return solution1(s);
        return solution2(s);
    }

    /**
     * 递归
     *
     * 类似 -> HJ50 四则运算
     *
     * @param s
     * @return
     */
    private String solution1(String s){
        int len = s.length();
        StringBuilder result = new StringBuilder();
        char ch;
        int num = 0;
        String part;
        for(int i=0; i<len; i++){
            ch = s.charAt(i);
            if(Character.isDigit(ch)){
                num = num*10 + (ch-'0');
            }

            if(ch == '['){
                int count = 1;
                char next;
                int j;
                for(j=i+1; j<len&&count>0; j++){
                    next = s.charAt(j);
                    if(next == '['){
                        count++;
                    }
                    if(next == ']'){
                        count--;
                    }
                    if(count == 0){
                        break;
                    }
                }
                part = decodeString(s.substring(i+1, j));
                while(num > 0){
                    result.append(part);
                    num--;
                }
                i = j;
            }

            if(Character.isLetter(ch)){
                result.append(ch);
            }
        }

        return result.toString();
    }

    /**
     * 栈
     * @param s
     * @return
     */
    private String solution2(String s){
        Stack<Integer> numStack = new Stack<>();
        Stack<String> resStack = new Stack<>();
        StringBuilder result = new StringBuilder();

        int len = s.length();
        char ch;
        int num = 0;
        for(int i=0; i<len; i++){
            ch = s.charAt(i);
            if(Character.isDigit(ch)){
                num = num*10 + (ch-'0');
            }

            if(ch == '['){
                numStack.push(num);
                num = 0;
                resStack.push(result.toString());
                result = new StringBuilder();
            }

            if(Character.isLetter(ch)){
                result.append(ch);
            }

            if(ch == ']'){
                int times = numStack.pop();
                StringBuilder part = new StringBuilder(resStack.pop());
                for(int j=1; j<=times; j++){
                    part.append(result);
                }
                result = part;
            }
        }

        return result.toString();
    }
}