Decode String Solutions in C++

// Source : https://leetcode.com/problems/decode-string/
// Author : Hao Chen
// Date   : 2016-09-08



class Solution {
public:
    string decodeString(string s) {
        if (!isValid(s)) return "";
        
        stack<string> _stack;
        stack<int> _nstack;
        
        string result;
        string tmp;
        int n=0;
        for (int i=0; i<s.size(); i++) {
            
            if ( isNum(s[i]) ) {
                n = 0;
                for(; isNum(s[i]); i++ ) {
                   n = n*10 + s[i] - '0'; 
                }
            }
            
            if (s[i] == '[') {
                tmp="";
                _stack.push(tmp);
                _nstack.push(n);
            } else if (s[i] == ']') {
                n = _nstack.top(); 
                tmp="";
                for (; n>0; n--) {
                    tmp += _stack.top();
                }
                _stack.pop();
                _nstack.pop();
                if ( ! _stack.empty() ) {
                    _stack.top() += tmp;
                }else {
                    result += tmp;
                }
            } else {
                if ( ! _stack.empty() ) {
                    _stack.top() += s[i];
                } else {
                    result += s[i];
                }
                
            }
        }
        
        return result;
    }
    
private:

    //only check the following rules:
    // 1) the number must be followed by '['
    // 2) the '[' and ']' must be matched.
    bool isValid(string& s) {
        stack<char> _stack;
        for (int i=0; i<s.size(); i++) {
            if ( isNum(s[i]) ) {
                for(; isNum(s[i]); i++);
                if (s[i] != '[') {
                    return false;
                } 
                _stack.push('[');
                continue;
            } else if (s[i] == ']' ) {
                if ( _stack.top() != '[' ) return false;
                _stack.pop();
            }
        }
        
        return (_stack.size() == 0);
    }
    
    bool isNum(char ch) {
        return (ch>='0' && ch<='9');
    }
};

/// Source : https://leetcode.com/problems/decode-string/description/
/// Author : liuyubobobo
/// Time   : 2018-09-29

#include <iostream>
#include <cassert>

using namespace std;


/// DFS - recursion algorithm
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string decodeString(string s) {
        int end;
        return dfs(s, 0, end);
    }

private:
    string dfs(const string& s, int start, int& end){

        string res = "";
        for(int i = start; i < s.size();)
            if(isalpha(s[i]))
                res += s[i++];
            else if(isdigit(s[i])){
                int j;
                for(j = i + 1; j < s.size() && isdigit(s[j]); j ++);
                int num = atoi(s.substr(i, j - i).c_str());
                assert(s[j] == '[');

                int e;
                string sub = dfs(s, j + 1, e);
                while(num --)
                    res += sub;

                assert(s[e] == ']');
                i = e + 1;
            }
            else{
                assert(s[i] == ']');
                end = i;
                return res;
            }

        end = s.size();
        return res;
    }
};


int main() {

    string s1 = "3[a]2[bc]";
    cout << Solution().decodeString(s1) << endl;
    // "aaabcbc"

    string s2 = "3[a2[c]]";
    cout << Solution().decodeString(s2) << endl;
    // "accaccacc"

    string s3 = "2[abc]3[cd]ef";
    cout << Solution().decodeString(s3) << endl;
    // "abcabccdcdcdef"

    return 0;
}

/// Source : https://leetcode.com/problems/decode-string/description/
/// Author : liuyubobobo
/// Time   : 2018-09-29

#include <iostream>
#include <cassert>
#include <vector>

using namespace std;


/// Using Stack - non recursion algorithm
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string decodeString(string s) {

        vector<string> stack;
        vector<int> nums;

        stack.push_back("");
        for(int i = 0; i < s.size();)
            if(isalpha(s[i]))
                stack.back() += s[i ++];
            else if(isdigit(s[i])){
                int j;
                for(j = i + 1; j < s.size() && isdigit(s[j]); j ++);
                nums.push_back(atoi(s.substr(i, j - i).c_str()));
                stack.push_back("");
                assert(s[j] == '[');
                i = j + 1;
            }
            else{
                assert(s[i] == ']');
                string tres = stack.back();
                stack.pop_back();

                int num = nums.back();
                nums.pop_back();

                while(num --)
                    stack.back() += tres;

                i ++;
            }
        return stack.back();
    }
};


int main() {

    string s1 = "3[a]2[bc]";
    cout << Solution().decodeString(s1) << endl;
    // "aaabcbc"

    string s2 = "3[a2[c]]";
    cout << Solution().decodeString(s2) << endl;
    // "accaccacc"

    string s3 = "2[abc]3[cd]ef";
    cout << Solution().decodeString(s3) << endl;
    // "abcabccdcdcdef"

    return 0;
}