C++ standard recursion solution with explanation.


  • 0
    F

    This problem is similar to the mini parser problem. There are three cases we need to handle. We use a variable to keep track of the multiplier. When the current character is a number, we update the multiplier. When the current character is [, call the function recursively starting from the idx after [. When the current character is a letter, simply add it to the output string.

    class Solution {
    public:
        string decodeString(string s) {
            int idx = 0;
            return parseMult(s, idx, 1);
        }
        
        string parseMult(const string& s, int& idx, int mult) {
            string cur = "";
            int nextMult = 0;
            while (idx < s.length() && s[idx] != ']') {
                if (isdigit(s[idx])) {
                    nextMult = 10*nextMult + s[idx] - '0';
                } else if (s[idx] == '[') {
                    ++idx;
                    cur += parseMult(s, idx, nextMult);
                    nextMult = 0;
                } else {
                    cur += string(1, s[idx]);
                }
                ++idx;
            }
            string result = "";
            for (int i=0; i<mult; ++i) result += cur;
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.