Given an encoded string, return it's decoded string.

Description

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".

Explain

这题的题意就是给一个字符串，然后根据描述的规则，将其变成目标的字符串。规则就是括号里面的字符串需要被重复括号前的数字次，如果没有括号包裹起来的字符串，就只有一次。这题不用DFS做，我感觉比较难想。使用DFS，就可以很简单做出来，下面上代码

Code

class Solution {
public:
    string decodeString(string s) {
        string ans = "";
        int start = 0;
        dfs(ans, start, s.length(), s);
        return ans;
    }
    
    bool isNum(char c) {
        return c >= '0' && c <= '9';
    }
    
    bool isZimu(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }
    
    void dfs(string& cur, int& i, int len, string origin) {
        string num = "";
        string zu = "";
        for (; i < len; i++) {
            char c = origin[i];
            if (isNum(c)) {
                num += c;
            }
            if (c == '[') {
                i++;
                dfs(zu, i, len, origin);
                int count = stoi(num);
                for (int j = 0; j < count; j++) cur += zu;
                zu = "";
                num = "";
            }
            
            if (c == ']') {
                return;
            }
            
            if (isZimu(c)) cur += c;
        }
    }
    
    
};