力扣394——字元串解碼
- 2020 年 2 月 19 日
- 筆記
這道題主要涉及的是對遞歸和棧的理解。
原題
給定一個經過編碼的字元串，返回它解碼後的字元串。
編碼規則為: k[encoded_string]，表示其中方括弧內部的 encoded_string 正好重複 k 次。注意 k 保證為正整數。
你可以認為輸入字元串總是有效的；輸入字元串中沒有額外的空格，且輸入的方括弧總是符合格式要求的。
此外，你可以認為原始數據不包含數字，所有的數字只表示重複的次數 k ，例如不會出現像 3a 或 2[4] 的輸入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
原題url：https://leetcode-cn.com/problems/decode-string/
解題
遞歸
這道題目，簡單來看就是根據數字和內容，進行不斷重複輸出，最終得出結果。因此，遞歸也是最容易讓人想到的。
數字代表內容需要重複的次數，[代表一次新的遞歸開始，]代表本次遞歸的結束，有點類似括弧匹配這種問題。只是需要記錄中間結果，以及最開始的s進過一次遞歸遍歷後的下標位置。
基於上面的講解，我們也就能夠寫出程式碼：
class Solution { public String decodeString(String s) { StringBuilder resultSb = new StringBuilder(); dfs(s, 0, resultSb); return resultSb.toString(); } public int dfs(String s, int index, StringBuilder resultSb) { // 需要重複的次數 int count = 0; while (index < s.length()) { char temp = s.charAt(index); // 如果是數字，則先累計進count中 if (temp >= '0' && temp <= '9') { count = count * 10 + temp - '0'; } // 遇到'['，則開始新一輪的遞歸 else if (temp == '[') { StringBuilder tempResult = new StringBuilder(); index = dfs(s, index + 1, tempResult); // 重複 for (int i = 0; i < count; i++) { resultSb.append(tempResult); } // count進行重置 count = 0; } // 遇到']'，結束遞歸 else if (temp == ']') { // 返回新的下標 return index; } // 遇到字母 else { resultSb.append(temp); } index++; } return index; } }
提交OK。
利用棧
既然有遞歸的寫法，那麼自然有不遞歸的寫法，這就需要藉助棧了。大家可以類比成計算一段普通的數學表達式，裡面有括弧、數字、符號運算等，所以需要兩個棧，分別存儲數字和運算符。
這道題目自然也是需要兩個棧的，一個用來存儲重複的次數，一個用來存儲中間的字元串結果。判斷出棧、入棧的依據，依據是[]，[代表數字和字元串都壓入相應的棧，]代表需要將數字和字元串都需要從棧首壓出，進行計算。
接下來看看程式碼：
class Solution { public String decodeString(String s) { // 存放次數的棧 Stack<Integer> countStack = new Stack<>(); // 存放字元串的棧 Stack<StringBuilder> sbStack = new Stack<>(); // 臨時存儲字元串的內容 StringBuilder tempSb = new StringBuilder(); // 臨時存儲數字的內容 int tempCount = 0; // 遍歷 for(char temp : s.toCharArray()) { // 如果是數字，則先累計進tempCount中 if (temp >= '0' && temp <= '9') { tempCount = tempCount * 10 + temp - '0'; } // 遇到'['，將之前的數字和字元串放進countStack中 else if (temp == '[') { countStack.push(tempCount); tempCount = 0; sbStack.push(tempSb); tempSb = new StringBuilder(); } // 遇到']'，從countStack拿出數字 else if (temp == ']') { // 重複 StringBuilder tempResult = new StringBuilder(); int count = countStack.pop(); for (int j = 0; j < count; j++) { tempResult.append(tempSb); } // 拿出sbStack第一個 StringBuilder sb = sbStack.pop(); tempSb = sb.append(tempResult); } // 遇到字母 else { tempSb.append(temp); } } return tempSb.toString(); } }
提交OK。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要涉及的是對遞歸和棧的理解，有點類似數學表達式的計算，只是做一下類比即可。
