[leetcode] Score of Parentheses

problem

code

1st try

/**
 * @param {string} S
 * @return {number}
 */
var scoreOfParentheses = function(S) {
    // ((()(()))): 2(2(1()+2(1()))) = (2*(2*((1)+(2*1))))
    // (()()): 2(1()+1()) => 000101
    
    const stack = [0];
    for (let i = 0; i < S.length; i++)
    {
        if (S[i] == '(')
        {
            stack.push(0);
        }
        else
        {
            const last = stack.pop();
            const lastMinusOne = stack.pop();
            stack.push(lastMinusOne + Math.max(last * 2, 1));
        }
    }
    return stack.pop();
    
};

Time: O(N)
Space: O(N)

ex) (()())
[ 0, 0( ]
[ 0, 0(, 0( ]
[ 0, 1 ] ) operation 0 + max(2 * 0, 1)
[ 0, 1, 0( ]
[ 0, 2 ] ) operation 1 + max(2*0, 1)
[ 4 ] ) operation 0 + max(2*2, 1)

2nd try

from leetcode "SlovakUnion"
The idea is a(x + y) <=> ax + ay

class Solution {
    public int scoreOfParentheses(String s) {
        int mult = 1;
        int score = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                if (s.charAt(i+1) == '(') {
                    mult *= 2;
                } else {
                    score += mult;
                    i++;
                } 
            } else {
                mult = mult/2;
            }
        }
        return score;
    }
}

TIME: O(N)
Space: O(1)