leetcode394:字符串解码
定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
eg:
输入：s = “3[a]2[bc]” 输出：“aaabcbc”
输入：s = “3[a2[c]]” 输出：“accaccacc”
输入：s = “2[abc]3[cd]ef” 输出：“abcabccdcdcdef”
输入：s = “abc3[cd]xyz” 输出：“abccdcdcdxyz”
递归：
本题解用原函数进行递归，用repeatCnt来记录左括号的层数，最外层进入下一级递归， 最外层以内的字符直接入栈。
class Solution {public: string decodeString(string s) {string temp,result; int tempCnt=0; int cnt = 0; int repeatCnt=0; for(int i=0;i<s.size();i ) {if(s[i]>=48&&(s[i]<=57)) {if(repeatCnt==0) {if(tempCnt) {tempCnt =tempCnt*10 s[i]-48; } else tempCnt=s[i]-48; } else {temp.push_back(s[i]); } } else if(s[i]>=97&&(s[i]<=122)) {if(repeatCnt==0) {result.push_back(s[i]); } else {temp.push_back(s[i]); } } else if(s[i]==91) {if(repeatCnt==0) {repeatCnt = 1; cnt = tempCnt; tempCnt = 0; } else {repeatCnt ; temp.push_back(s[i]); } } else if(s[i]==93) {if(repeatCnt>1) {repeatCnt--; temp.push_back(s[i]); } else {temp = decodeString(temp); for(int i=0;i<cnt;i ) {for(int j=0;j<temp.size();j ) {result.push_back(temp[j]); } } repeatCnt--; temp.clear(); } } } return result; }};
需要注意的时，每一次调用temp结束后都需要做clear的操作。另外，string的push_back只能加入一个字符， 如果采用append, 就可以加入一个字符串。
赞 (0)