每日题解:LeetCode 394. 字符串解码
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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".
解法
java
//解析字符串，遇到数字进入栈，遇到[ 进入 遇到] 开始输出
public String decodeString(String s) {
char[] sArr= s.toCharArray();
LinkedList<Integer> stackNum = new LinkedList<>();
LinkedList<String> stackString = new LinkedList<>();
int num = 0;
StringBuffer res=new StringBuffer();
for (char c : sArr) {
//获取到数字
if(Character.isDigit(c)){
num = num*10+Integer.parseInt(String.valueOf(c));
} else if(c=='['){
//将获取到的数字存入到栈，并且存入之前的字符，开始重写计数
//stackNum和stackString stackNum[i] stackString[i]记录之前的字符串
stackNum.add(num);
stackString.add(res .toString());
num=0;
res =new StringBuffer();
}else if(c==']'){
StringBuffer temp=new StringBuffer();
int temp_num=stackNum.removeLast();
//cc
for (int i = 0; i < temp_num; i++) {
temp.append(res);
}
//合并到acc
res = new StringBuffer(stackString.removeLast() + temp);
}else if(Character.isLetter(c)){
res.append(c);
}
}
return res.toString();
}
C++
public:
static string decodeString(string s){
size_t num = 0;
vector<int> stackNum;
vector<string> stackString ;
string res;
for (int i = 0; i < s.size(); i++) {
char c=s[i];
if (isdigit(c)) {
//用char进行计算时，需要减去48.字符转换为数值
num=num*10+c - '0';
}else if(c=='['){
stackNum.push_back(num);
stackString.push_back(res);
num=0;
res ="";
}else if(c==']'){
int count = stackNum.back();
stackNum.pop_back();
string resTemp=res;
for (int k = 1; k < count; k++)
{
resTemp.append(res);
}
res = stackString.back() + resTemp;
stackString.pop_back();
}else if(isalpha(c)){
//是否为字母
res.push_back(c);
}
}
return res;
}
解题思路
栈
1.分析实例
如果字符串s=3[a2[c]]，输出accaccacc，从这个实例可出，本题是一个按照特定的规则解析字符，如2[c]表示cc，表示两个c的字符缩减，如果存在嵌套，从内到外的顺序解析字符。
1.2再解析外部3[acc]
说个题外话，这个规则的解析让我想到了redis的[RESP](https://redis.io/topics/protocol)协议。
*3\r\n
$3\r\n
foo\r\n
$-1\r\n
$3\r\n
bar\r\n
表示 ["foo",nil,"bar"]
2.寻找规则
从走到右读取字符串的字符，如果读到数字，表示我接下来[]内的字符需要重复的次数；读取到[，表示需要接下来的内容是我需要输出的字符，直到读取到]结束。
s = "3[a]2[bc]", 返回 "aaabcbc".
如果遇到嵌套的[],优先解析最内部的字符，然后逐步从后往前输出。
s = "3[a2[c]]", 返回 "accaccacc"
我们得到规则
2.1从左往右读取规则
2.2最先读取的规则，最后输出
2.3一个完整[]，表示一个输出字段，遇到[开始记录，到]结束。
从第二个规则，得出"后进先出"，符合栈的规则，LIFO。
3.代码实现
3.1 定义两个栈，一个记录数字，一个记录字符
这里我们使用了LinkedList，LinkedList可以底层使用双向链表实现
-24207cff5a484b3389a85c1a2d420bb2.png)
所以，LinkedList可以表示栈和队列(实现了Deque）
LinkedList<Integer> stackNum = new LinkedList<>();
LinkedList<String> stackString = new LinkedList<>();
定义一个StringBuffer 拼接我们的解析结果
StringBuffer res=new StringBuffer();
3.1遍历读取字符
char[] sArr= s.toCharArray();
for (char c : sArr) {
}
读取数字字节
if(Character.isDigit(c)){
num = num*10+Integer.parseInt(String.valueOf(c));
}
使用Character.isDigit(char c)判断当前的读取中的字节，是不是数字，由于考虑到数字不一定是个位数，可能是十位，百位，所以我们使用一个变量num，每次*10，加上当前的数字
这里我们先把剩余方法的框架写好
//遇到[
else if(c=='['){
//遇到]
}else if(c==']'){
//遇到字符字节
}else if(Character.isLetter(c)){
}
处理字符字节
我们可以使用3[a2[c]]作为我们的解析例子，方便我们理解
遇到[
当遇到[,例子中第一个[,不方便理解，我们先将方法空着，直接跳到第二个]，进行解析。
当读取到[，表示我们开始读取[]的字符，这里我们需要初始化之前指针或者临时变量，也可以理解为我们清空上一个读取的数据，把之前的读取的数据存到栈中。
num=0;
res =new StringBuffer();
同时我们需要将上一次读取到的数据存到栈中
stackNum.add(num);
stackString.add(res .toString());
遇到]
当读取到一个]，我们需要将解析一个N[]
首先我们需要知道重复的个数，读取数字栈顶的元素，可以从上一个读取**遇到[**存入的方式值的，数字栈顶部的元素就是我们读取N[]中数字N。
int temp_num=stackNum.removeLast();
循环拼接我们暂存的字符
StringBuffer temp=new StringBuffer();
for (int i = 0; i < temp_num; i++) {
temp.append(res);
}
由于每次遇到[,我们会将res清空，所以res就是N[]中[]之间的字符
合并字符
res = new StringBuffer(stackString.removeLast() + temp);
每次遇到[,我们会将res存到字符栈最后一个元素，字符栈的栈顶元素就是之前的字符
字节
遇到字节拼接到当前res中
else if(Character.isLetter(c)){
res.append(c);
}