LeetCode 394. 字符串解碼

題目描述

給定一個經過編碼的字符串，返回它解碼后的字符串。
編碼規(guī)則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次。注意 k 保證為正整數(shù)。
你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。
此外，你可以認為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復的次數(shù) k ，例如不會出現(xiàn)像 3a 或 2[4] 的輸入。

思路

思路：參考的題解字符串解碼（輔助棧法 / 遞歸法，清晰圖解）
在這個題解中的變量包括res臨時存儲字符串，multi臨時存儲數(shù)值，stack_multi作為輔助棧存儲數(shù)值，stack_res作為輔助棧存儲字符串，在這個算法中，規(guī)則為：

1. 假如遇到了數(shù)字，更新multi=10*multi+Integer.parse(c+””);
2. 假如遇到了字符，更新res=res.append(c)
3. 假如遇到了[，將multi和res中的內容入棧：multi.push(multi), res.push(res)并做清空multi=0, res=new StringBuilder()
4. 假如遇到了]，將stack_multi和stack_res中的內容出棧，得到目前的結果寫入res中。實際上就是res=last_res+last_multi*res，即有：
   I. Integer m = stack_multi.pop(); String r = stack_res.pop()
   II. 根據(jù)值m和當前res中的內容，利用for循環(huán)組成字符串for(int i=0;i<m;i++) tmp.append(res)
   III. res=r+tmp

代碼

class Solution {public String decodeString(String s) {StringBuilder res = new StringBuilder();int multi = 0;// 兩個輔助棧，一個存數(shù)字，一個存字符串Deque<Integer> stack_multi = new ArrayDeque<>();Deque<String> stack_res = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '['){ // 如果等于左括號，將res和multi入棧中stack_multi.push(multi);stack_res.push(res.toString());multi = 0;res = new StringBuilder();} else if (c == ']') { // 如果等于右括號，當前結果=last_res+last_multi*resInteger last_multi = stack_multi.pop();String last_res = stack_res.pop();StringBuilder tmp = new StringBuilder();for (int i = 0; i < last_multi; i++) tmp.append(res);res = new StringBuilder(last_res + tmp);}else if (c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");else res.append(c);}return res.toString();}
}