O(n) time O(n) space C++ iterative solution using stack + map


  • 0
    V
    class Solution {
    public:
        string countOfAtoms(string f) {
            int fact = 1, i = f.length()-1, local_fact = 1; // traverse string from backward
            stack<int> s;
            map<string, int> m;
            string pre = "", ans;
            while (i >= 0) {
                if (isupper(f[i])) { // upper case means we've got one complete element
                    pre = f[i] + pre;
                    m[pre] += local_fact * fact;
                    pre = "";
                    local_fact = 1;
                    i--;                
                }
                else if (islower(f[i])) { // we continue till we encounter upper case
                    pre = f[i] + pre;
                    while (islower(f[--i]))
                        pre = f[i] + pre;
                }
                else if (isdigit(f[i])) { // we continue till we get complete number 
                    local_fact *= (f[i] - '0');
                    int j = 1;
                    while (isdigit(f[--i])) {
                        local_fact += (f[i] - '0') * pow(10, j++); 
                    }
                }
                else if (f[i] == ')') { // closing brace, items to it's left are multiplied by fact; deep by 1 level
                    s.push(local_fact);
                    fact *= local_fact;
                    local_fact = 1;
                    i--;
                }
                else if (f[i] == '(') { // coming op one level, discard factor attributed to it
                    fact /= s.top();
                    s.pop();
                    i--;
                }
            }
            for (auto kv : m) {
                ans +=  kv.first;
                if (kv.second > 1)
                    ans += to_string(kv.second);
            }
            return ans;
        }
    };
    

Log in to reply
 

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