# [leetcode] Score of Parentheses

victor·2021년 2월 25일
0

목록 보기
39/63

## 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)

캬-!