字符串解码分析

不点 阅读:312 2020-10-27 22:26:32 评论:0

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

编码规则为: 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".

 

解:这题我用的递归法,但有一个条件算错了导致通不过全部案例,暂时先记录下

class Solution { 
public: 
    //i作为[括号后的第一个字符 
    string decodeRes(string &s,int i) 
    { 
         
        string tmp; 
        string str_ret; 
        int nums=0; 
        while(i<s.size()) 
        { 
            if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')) 
            { 
                  tmp+=s[i]; 
            } 
            //数字可能不止1位,要考虑 
            else if(s[i]>='0'&&s[i]<='9') 
            { 
                nums=nums*10; 
                nums+=s[i]-'0';   
            } 
            else if(s[i]=='[') 
            { 
                 
                //递归调用 
                str_ret =decodeRes(s,i+1); 
                while(nums) 
                { 
                    tmp+=str_ret; 
                    nums--; 
                } 
                //跳过已经递归过的,这样写是错的,因为返回的字符串已经展开过了 
                i+=str_ret.size()+1; 
            } 
            else if(s[i]==']') 
            { 
                return tmp; 
            } 
            i++; 
        } 
        return tmp; 
    } 
    string decodeString(string s) { 
        if(s.size()==0) 
            return ""; 
        //总字符串 
        return decodeRes(s,0); 
    } 
};

 

标签:C++
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

一个IT知识分享的公众号