给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
题解
辅助栈法
一、一个栈存储数字,一个存储字符串
二、从左到右遍历每个字符,分四种情况:
1.数字
对于数字,要注意题目条件:s 中所有整数的取值范围为 [1, 300] ,也就是数字有可能是不止一位的,数字结束的标志是遇到[
2.左括号[
遍历到左括号,我们让当前字符串curString和当前数字curNum分别入自己的栈。
同时让它们回归初始值""和0
3.右括号]
遍历到右括号,那就可以进行解码操作了。
具体而言,就是弹出数字栈的元素,作为要循环的次数num,弹出字符串栈的元素tmp,在tmp后面拼接num个curString
最后将curString置为tmp
4.字符
如果是字符,直接拼接在当前字符串后面
三、返回值
curString
class Solution {public String decodeString(String s) {Stack<Integer> numStack = new Stack<>();Stack<String> strStack = new Stack<>();String curString="";int cuNum=0;for(int i=0;i<s.length();i++){char c=s.charAt(i);//1.c是数字//要考虑数字为两位数或者三位数的情况if(c<='9'&&c>='0') cuNum=cuNum*10+c-'0';//2.c是左括号//此时将curString和curNum都入栈else if(c=='['){numStack.push(cuNum);strStack.push(curString);cuNum=0;curString="";} //3.c是右括号//开始计算else if(c==']'){int num=numStack.pop();String tmp=strStack.pop();//注意这块是>0而不是>=0while(num>0){tmp+=curString;num--;}curString=tmp;}else{//此时c为字符curString+=c;}}return curString;}
}