c++, recursive and stack solution, both 0ms


  • 0

    stack solution

    string decodeString(string s) {
        if (s.size()<=3) return s;
        stack<string> strs;
        stack<int> cnt;
        cnt.push(1);
        strs.push("");
        string res="";
        int i=0;
        while(i<s.size()){
            if (isdigit(s[i])){
                int x=0;
                while(isdigit(s[i])){
                    x=x*10+s[i]-'0';
                    i++;
                }
                cnt.push(x);
            }else if(isalpha(s[i])){
                int j=i;
                while(j<s.size()&&isalpha(s[j])) j++;
                string temp=s.substr(i,j-i);
                i=j;
                strs.top()+=temp;
            }else if (s[i]=='['){
                i++;
                strs.push("");
            }else if(s[i]==']'){
                i++;
                string temp=strs.top();
                strs.pop();
                for (int i=0;i<cnt.top();i++){
                    strs.top()+=temp;
                }
                cnt.pop();
            }
        }
        return strs.top();
    }
    

    recursive solution

    string decodeString(string s) {
        if(s.size()<=3) return s;
        int i=0,ld=0,rd=0,lb,rb;
        while(i<s.size()){
            if (isalpha(s[i])) i++;
            else {
                ld=i;
                while(s[i]!='[') i++;
                string pre = s.substr(0,ld);
                int k = stoi(s.substr(ld,i-ld));
                i++;
                lb = i;
                int cnt=1;
                while(cnt!=0){
                    if (s[i]=='[') cnt++;
                    else if (s[i]==']') cnt--;
                    i++;
                }
                rb=i-2;
                string curDuplicate = decodeString(s.substr(lb,rb-lb+1));
                while(k>0){
                    pre+=curDuplicate;
                    k--;
                }
                pre+=decodeString(s.substr(i));
                return pre;
            }
        }
        return s;
    }

Log in to reply
 

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