题解 | #牛牛的字符串解码问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String decodeString (String s) {
        // write code here
        int n = s.length();
        char[] ch = s.toCharArray();
        int[] idx = new int[n];
        StringBuilder sb =new StringBuilder();
        //用栈保存每个[所对应的]的下标
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i < n ;i++){
            if(ch[i] == '['){
                dq.push(i);
            }else if(ch[i] == ']'){
                idx[dq.pop()] = i;
            }
        }
        return dfs(ch, idx, 0, n - 1).toString();
    }
    //递归求每个区间[l, r]内的字符串
    StringBuilder dfs(char[] ch, int[] idx, int l, int r){
        if(l > r){
            return new StringBuilder();
        }
        //初始化字符串
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for(int i = l; i <= r; i++){
            //如果当前字符为数字
            if(Character.isDigit(ch[i])){
                cnt = cnt * 10 + (ch[i] - '0');
            }else if(ch[i] == '['){ 
                int next = idx[i];
                //取得下一个区间的字符串nextStr
                StringBuilder nextStr = dfs(ch, idx, i + 1, next - 1);
                i = next;
                //将cnt次字符串添加在初始字符串中
                for(int j = 0; j < cnt; j++){
                    sb.append(nextStr);
                }
                cnt = 0;
            }else{
                //如果是字母，则加入初始字符串
                sb.append(ch[i]);
                cnt = 0;
            }
        }
        return sb;
    }
}