Leetcode 394. Decode String

medium

Solution 1

class Solution {
public:
    string getSub(int rep, string& s, int startPos, int& endPos) {
        cout << rep << ":" << startPos << endl;
        int i = startPos;
        string numStr = "";
        string ret = "";
        string str = "";
        string sub = "";
        while(true) {
            if (s[i] >= '0' && s[i] <= '9') {
                numStr += s[i];
                i++;
            } else if (s[i] == '[') {
                str += getSub(std::stoi(numStr), s, i+1, endPos);
                numStr = "";
                i = endPos + 1;
            } else if (s[i] == ']' || i == s.size()) {
                endPos = i;
                break;
            } else {
                str += s[i];
                i++;
            } 
        }
        
        if (!rep)
            rep = 1;
        for (int i=0; i<rep; i++) {
            ret += str;
        }
        return ret;  
    }
    string decodeString(string s) {
        string ret;
        int j = 0;
        for (int i=0; i< s.size();) {
            ret += getSub(1, s, i, j);
            cout << ret << endl;
            i = (j+1);
        }
       return ret;
    }
    
};

Solution 2

class Solution {
    vector<string> stack;
public:
    string decodeString(string s) {
        int i = 0;
        string num;
        for (int i=0; i<s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num += s[i];
            } else if (s[i] == '[') {
                stack.push_back(num);
                num = "";
                stack.push_back(string(1, s[i]));
            } else if (s[i] == ']') {
                string temp;
                string top;
                do{  
                    top = stack.back();
                    stack.pop_back();
                    temp = top + temp;
                } while (top[0] != '[');
                top = stack.back();
                stack.pop_back();
                int n = std::stoi(top);
                string temp2;
                for (int j=0; j<n; j++) {
                    temp2 += temp.substr(1);
                }
                stack.push_back(temp2);          
            } else {
                stack.push_back(string(1, s[i]));
            }    
        }
        
        string ret;
        for (int i=0; i<stack.size(); i++) {
            ret += stack[i];
        }
        return ret;
    }
};