Leetcode 394. 字符串解码

题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试样例

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

题解

栈应用
用两个栈分别存储重复的次数、括号以及重复的字符串
我们用一个变量now记录当前需要重复的字符串。
如果是数字，我们需要压入数字及之后的左括号，同时将now设为空。
字母我们需要用now进行堆积，
如果是]，我们需要判定栈顶是不是[，如果不是我们首先需要把字符串进行拼接，直至栈顶为左括号，然后再弹出数进行重叠，之后再压入栈中。是[，则直接进行重复，然后压入栈中。
详细过程见代码

代码

string decodeString(string s) {stack<int> num;stack<string> op;int len = s.length();string ans;string now = "";op.push("");for(int i=0; i<len; i++){if(s[i] == '['){		//把我们的数字和[压入栈中if(now == ""){num.push(1);}else   num.push(stoi(now));op.push("[");now = "";}else if(s[i]==']'){if(op.top() == "["){		//直接进行重叠op.pop();   string newNow="";if(now != ""){int time = num.top();while(time--){newNow += now;}}  if(op.top()!="["){	//如果去掉[后栈中还有字符串，那么需要和我们现在的进行拼接，作为新的需要重复的字符串newNow = op.top() + newNow;op.pop();}op.push(newNow);num.pop();}else{		//栈中还有其他需要重叠的字符串，我们现进行拼接now = op.top()+now;op.pop();op.pop();	//弹出的是左括号int time = num.top();num.pop();string newNow="";while(time--){newNow += now;}if(op.top()!="["){	//如果去掉[后栈中还有字符串，那么需要和我们现在的进行拼接，作为新的需要重复的字符串newNow = op.top() + newNow;op.pop();}op.push(newNow);}now = "";}else if(s[i]>='0' && s[i]<='9'){		//数字，我们获取数字if(now != ""){		//之前有需要重复的字符串，我们需要将近压入栈中if(op.top() != "["){now = op.top() + now;op.pop();}op.push(now);now = "";}while(i<len && s[i]>='0' && s[i]<='9')now += s[i++];i--;}else{		//堆积字母now += s[i];}}return op.top()+now;}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。