leetcode 394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
题解：
1.一个经过编码的字符串
2.返回它解码后的字符串
3.输入字符串总是有效的;没有额外的空格;方括号总是符合格式要求
4.数字只表示重复的次数
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
解题思路：数字栈和字母栈
-
数字栈push遍历到的数字(只表示重复次数)，字母栈存放遍历的字母
-
遍历到左括号"["时，分别把遍历到的数字和上一个字母入栈
-
遍历到右括号"]"时，分别从数字栈pop重复次数，左括号"["和右括号"]"之间的字母用临时变量记录(要重复的字母)，与字母栈顶元素重复拼接称字符串放到字母栈顶
-
更新临时变量，并弹出当前栈顶元素，若再遇到右括号"]"重复上述过程，直到遍历到原始压缩字符串尾
C/C++题解：
class Solution {
public:
string decodeString(string s) {
int len = s.size();
int num = 0;
stack<int> numstack; //数字栈
stack<string> alpstack; //字符栈
string cur = "";
for(int i=0; i<len; i++){
if(s[i]>='0' && s[i]<='9'){
num = 10*num + s[i] - '0';}//连续数字字符变成数值
else if(s[i] == '['){ //数字字符后遇到左括号开始入栈
numstack.push(num);//数字放数字栈
alpstack.push(cur);//字母放字母栈
num = 0;//重置数字
cur.clear();//重置字母串
}//左括号后遇到字母
else if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z'))
cur += s[i];//记录下来
else if(s[i] == ']')//直到遇到右括号
{//弹出栈
int k = numstack.top();//获取重复字母串次数
numstack.pop();
for(int j=0; j<k; j++)//与栈顶元素循环次数拼接
alpstack.top() += cur;
//栈顶元素+K*cur
cur = alpstack.top();//获取拼接好的字符串
alpstack.pop();}}//从栈里弹出
return cur;}};
Debug结果：
Java题解：
class Solution {
public String decodeString(String s) {
int len = s.length();
int num = 0;
Stack<Integer> numstack = new Stack<Integer>(); //数字栈
Stack<String> alpstack = new Stack<String>(); //字符栈
String cur = "";
char[] str = s.toCharArray();
for(int i=0; i<len; i++){
if(str[i]>='0' && str[i]<='9'){
num = 10*num + str[i] - '0';
}//连续数字字符变成数值
else if(str[i] == '[')
{ //数字字符后遇到左括号开始入栈
numstack.push(num);//数字放数字栈
alpstack.push(cur);//字母放字母栈
num = 0;//重置数字
cur = "";//重置字母串
}//左括号后遇到字母
else if((str[i]>='a' && str[i]<='z') || (str[i]>='A' && str[i]<='Z'))
cur += str[i];//记录下来
else if(str[i] == ']')//直到遇到右括号
{//弹出栈
int k = numstack.pop();//获取重复字母串次数
// numstack.pop();
String tmp = alpstack.peek();
for(int j=0; j<k; j++)//与栈顶元素循环次数拼接
tmp += cur;
//栈顶元素+K*cur
cur = tmp;//获取拼接好的字符串
alpstack.pop();}}//从栈里弹出
return cur;}}
Debug结果：
Python题解：
class Solution(object):
def decodeString(self, s):
""":type s: str:rtype: str"""
num = 0
numstack = [] #数字栈
alpstack = [] #字符栈
cur = ""
for ch in s:
if(ch>='0' and ch<='9'):
num = 10*num + int(ch)
#连续数字字符变成数值
elif ch == '[':
#数字字符后遇到左括号开始入栈
numstack.append(num)#数字放数字栈
alpstack.append(cur)#字母放字母栈
num = 0#重置数字
cur = ""#重置字母串
#左括号后遇到字母
elif (ch>='a' and ch<='z') or (ch>='A' and ch<='Z'):
cur += ch#记录下来
elif(ch == ']'):#直到遇到右括号
#弹出栈
k = numstack.pop()#获取重复字母串次数
tmp = alpstack[-1]
for j in range(k):#与栈顶元素循环次数拼接
tmp += cur
#栈顶元素+K*cur
cur = tmp #获取拼接好的字符串
alpstack.pop()#从栈里弹出
return cur
Debug结果：
更多题解移步公众号免费获取