c++ simple solution, recursive and stack


  • 0
    H

    recursive

    class Solution {
        string help(string &s, int &i) {
            string ans;
            for (; i < s.size() && s[i] != ']'; ) {
                if (isalpha(s[i])) {
                    ans.push_back(s[i++]);
                }
                else {
                    int numStart = i;
                    for (++i; isdigit(s[i]); ++i) ;
                    int repeat = stoi(s.substr(numStart, i - numStart));
                    string word = help(s, ++i);
                    for (; repeat > 0; --repeat) {
                        ans.append(word);
                    }
                    ++i;
                }
            }
            return ans;
        }
    public:
        string decodeString(string s) {
            int i = 0;
            return help(s, i);
        }
    };
    

    stack version

    string decodeString(string s) {
            stack<string> stk;
            stk.push("");
            for (int i = 0; i < s.size();) {
                if (isalpha(s[i])) {
                    stk.top().push_back(s[i++]);
                }
                else if (isdigit(s[i])) {
                    int numStart = i;
                    for (++i; isdigit(s[i]); ++i) ;
                    stk.push(s.substr(numStart, i - numStart));
                    stk.push("");
                    ++i;
                }
                else {
                    string word = stk.top(); stk.pop();
                    int repeat = stoi(stk.top()); stk.pop();
                    for (; repeat > 0; --repeat) {
                        stk.top().append(word);
                    }
                    ++i;
                }
            }
            return stk.top();
        }
    

Log in to reply
 

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