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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。