LeetCode 394 Decode String 题解

题意简述：给定一个解码规则k[encoded_string] -> encoded_string重复k次，以及一个根据此规则编码的字符串，求出解码后的字符串。
输入：编码的字符串s
输出：解码后的字符串
示例：字符串“3[a2[c]]”将被解码为“accaccacc”,3[a2[c]]=3[acc]=accaccacc

题解：
涉及到括号匹配和嵌套，因而采用DFS进行求解。
设置一个int记录当前处理的字符在字符串的下标cur，记在当前dfs函数中用来存放结果的字符串res。考虑当前处理的字符，只有4种可能：

代码实现如下：

class Solution {
private:
    int curind;
    string mystr;

    string dfs() {
        string res;

        while(curind < mystr.size()) {
            if(isalpha(mystr[curind])) {
                res.push_back(mystr[curind]);
                curind++;
            }

            if(isdigit(mystr[curind])) {
                int rep = 0;
                while(isdigit(mystr[curind])) {
                    rep = rep * 10 + (mystr[curind] - '0');
                    curind++;
                }

                curind++;
                string temp = dfs();
                for(int i = 0;i < rep;i++) res += temp;
            }

            if(mystr[curind] == ']') {
                curind++;
                return res;
            }
        }

        return res;
    }
public:
    string decodeString(string s) {
        curind = 0;
        mystr = s;
        return dfs();
    }
};