Decode String

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = “3[a]2[bc]”, return “aaabcbc”.
s = “3[a2[c]]”, return “accaccacc”.
s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

解码字符串，字符串内嵌套字符串，这种嵌套问题看到就想到用递归来解。仔细分析这种字符，我们发现数字后面必然是’[’，’]‘可以作为子串解码结束的标志符。我们逐个分析字符，遇到字符就加到结果里，遇到数字就解码出数字，因为数字后面必然后’[’+新的子字符串，那么下面的子串就可以用递归去解了，将解得的结果复制k倍加到结果上。其中，我们需要一个索引标志符来遍历整个字符串，当索引超出字符串或者索引指向’]'的时候就退出当前循环，返回解码结果。

class Solution {
public:
    string decodeString(string s) {
        if (s.empty()) return s;
        int index=0;
        return helper(s,index);
    }
    
    string helper(string s,int& index)
    {
        string res="";
        while(index<s.size()&&s[index]!=']')
        {
            if (s[index]>='a'&&s[index]<='z'||s[index]>='A'&&s[index]<='Z')
            {
                res+=s[index];
                index++;
            }
            else if (s[index]>='0'&&s[index]<='9')
            {
                int number=0;
                while(index<s.size()&&s[index]>='0'&&s[index]<='9')
                {
                    //cout<<number<<" "<<s[index]-'0'<<endl;
                    number=number*10+s[index]-'0';
                    index++;
                }
                cout<<number;
                index++;  // skip the '['
                string tmp=helper(s,index);
                while(number-->0) res+=tmp;
                index++;   // skip the ']'
            }
        }
        
        return res;
    }
};