【問題描述】[中等]

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

【解答思路】

1. 輔助棧法

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

public String decodeString(String s) {StringBuilder res = new StringBuilder();int multi = 0 ; LinkedList<Integer> stack_multi = new LinkedList<>();LinkedList<String> stack_res = new LinkedList<>();for(Character c: s.toCharArray()){if(c == '['){stack_multi.addLast(multi);stack_res.addLast(res.toString());multi = 0;res = new StringBuilder();}else if(c == ']'){StringBuilder tmp = new StringBuilder();int cur_multi =stack_multi.removeLast();for(int i = 0;i<cur_multi;i++){tmp.append(res);}res = new StringBuilder(stack_res.removeLast()+tmp);}else if(c >='0' && c<='9'){//次數(shù)大于10時(shí)需要累計(jì)multi = multi *10 +Integer.parseInt(c+"");}else{res.append(c);}}return res.toString();}

2. 遞歸法

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

class Solution {//空間換時(shí)間，同時(shí)避免遞歸傳這種不會(huì)改變的參數(shù)//String.charAt()會(huì)多一個(gè)越界的判斷，其實(shí)這里不轉(zhuǎn)為數(shù)組也可以，個(gè)人習(xí)慣char[] ss;public String decodeString(String s) {this.ss = s.toCharArray();return dfs(0)[0];}private String[] dfs(int i) {int nums = 0;StringBuilder res = new StringBuilder();while (i < ss.length) {//是數(shù)字，因?yàn)椴灰欢ㄖ挥袀€(gè)位，所以需要進(jìn)位計(jì)算if (Character.isDigit(ss[i])) {nums = nums * 10 + (ss[i] - '0');//如果是'['，就是重復(fù)字符串的開始位置} else if (ss[i] == '[') {//因?yàn)榭赡軙?huì)嵌套n[字符串]，所以需要進(jìn)入遞歸String[] temp = dfs(i + 1); //這里是16行//將指針移動(dòng)到結(jié)尾的']'位置，中間的內(nèi)容在下面的while中已經(jīng)填充完畢i = Integer.parseInt(temp[0]);//根據(jù)nums循環(huán)填充目標(biāo)字符串while (nums > 0) {res.append(temp[1]);nums--;}//如果是']'，說明已經(jīng)輸出完成，其實(shí)只在進(jìn)入遞歸后有效，第一次調(diào)用dfs的棧幀永遠(yuǎn)不會(huì)走進(jìn)這個(gè)判斷} else if (ss[i] == ']') {//此處為什么是i呢？因?yàn)檫@層return到的是遞歸方法調(diào)用處，即返回至16行所在，不可能返回到初次調(diào)用的位置//所以需要記錄']'出現(xiàn)的位置，至于為什么不+1，是因?yàn)樽咄?6行所在的代碼塊會(huì)走到34行return new String[]{String.valueOf(i), res.toString()};//類似于2[abc]3[cd]ef中的ef，沒有循環(huán)次數(shù)，可以直接填充} else {res.append(ss[i]);}//移動(dòng)指針i++; //這里是34行}return new String[]{res.toString()};} } class Solution {public String decodeString(String s) {return dfs(s, 0)[0];}private String[] dfs(String s, int i) {StringBuilder res = new StringBuilder();int multi = 0;while(i < s.length()) {if(s.charAt(i) >= '0' && s.charAt(i) <= '9') multi = multi * 10 + Integer.parseInt(String.valueOf(s.charAt(i))); else if(s.charAt(i) == '[') {String[] tmp = dfs(s, i + 1);i = Integer.parseInt(tmp[0]);while(multi > 0) {res.append(tmp[1]);multi--;}}else if(s.charAt(i) == ']') return new String[] { String.valueOf(i), res.toString() };else res.append(String.valueOf(s.charAt(i)));i++;}return new String[] { res.toString() };} }

【總結(jié)】

1.為什么用LinkedList不用Stack

基于 Vector 實(shí)現(xiàn)的棧 Stack底層是數(shù)組 擴(kuò)容開銷大
Java并不推薦使用java.util.stack來進(jìn)行棧的操作，而是推薦使用一個(gè)雙端隊(duì)列deque
詳情鏈接：https://www.cnblogs.com/cosmos-wong/p/11845934.html

2.細(xì)節(jié)

2.1 轉(zhuǎn)字符串
1、toString，需要保證調(diào)用這個(gè)方法的類、方法、變量不為null，否則會(huì)報(bào)空指針。

2、String.valueOf。這個(gè)方法在使用的時(shí)候是有些特殊的。一般情況下，如果是確定類型的null傳入，返回的是字符串“null”，而如果直接傳入null，則會(huì)發(fā)生錯(cuò)誤。

3、(String) 字符串類型強(qiáng)轉(zhuǎn)。需要保證的是類型可以轉(zhuǎn)成String類型。

2.2 、2.3 應(yīng)用于提取字符串中的數(shù)字字符轉(zhuǎn)整形

2.2 字符轉(zhuǎn)整型

Integer.parseInt(c + "");

2.3 字符串中某字符轉(zhuǎn)整型

Integer.parseInt(String.valueOf(s.charAt(i)));

3.括號(hào)匹配 棧棧棧

4.包裝類的用法

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
參考鏈接：https://blog.csdn.net/yangzhaomuma/article/details/51173138

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第394题][字符串解码][栈][类型转换]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。