0ms recursive c++ solution


  • 0
    M
    class Solution {
    public:
        string parse(string s) {
            string r = "";
            for(int i = 0; i < s.size();) {
                if(isdigit(s[i])) {
                    int num = 0;
                    while(isdigit(s[i])) {
                        num = num * 10 + (s[i] - '0');
                        ++i;
                    }
                    int bracket_match = 1;
                    int j = i;
                    while(bracket_match > 0) {
                        ++j;
                        if(s[j] == '[') ++bracket_match;
                        else if(s[j] == ']') --bracket_match;
                    }
                    string temp = parse(s.substr(i + 1, j - i - 1));
                    for(int k = 0; k < num; ++k) {
                        r += temp;
                    }
                    i = j + 1;
                } else if(isalpha(s[i])) {
                    r += s[i];
                    ++i;
                }
            }
            return r;
        }
        string decodeString(string s) {
            return parse(s);
        }
    };
    

  • 0
    J

    Thanks for the clear solution. A few comments are added:

             // following the digits, s[j] = '[', which should be always true
                int bracket_match = 1;
                int j = i;
                assert(s[i] == '[');
                
                // find the matching ']' for '['
                while(bracket_match > 0) {
                    ++j;
                    if(s[j] == '[') ++bracket_match;
                    else if(s[j] == ']') --bracket_match;
                }
                
                // extract the encoded_string in k[encoded_string]
                string temp = parse(s.substr(i + 1, j - i - 1));
                
                // repeat the parsed encoded_string num times
                for(int k = 0; k < num; ++k) {
                    r += temp;
                }
                // set the new start position, which is after ']'
                i = j + 1;

Log in to reply
 

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