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; } }