856. Score of Parentheses
Given a balanced parentheses string S
, compute the score of the string based on the following rule:
()
has score 1AB
has scoreA + B
, where A and B are balanced parentheses strings.(A)
has score2 * A
, where A is a balanced parentheses string.
Example 1:
Input: "()" Output: 1
Example 2:
Input: "(())" Output: 2
Example 3:
Input: "()()" Output: 2
Example 4:
Input: "(()(()))" Output: 6
Note:
S
is a balanced parentheses string, containing only(
and)
.2 <= S.length <= 50
Rust Solution
struct Solution;
impl Solution {
fn score_of_parentheses(s: String) -> i32 {
let mut stack: Vec<i32> = vec![];
for c in s.chars() {
if c == '(' {
stack.push(0);
} else {
let mut sum = 0;
while let Some(last) = stack.pop() {
if last != 0 {
sum += last;
} else {
break;
}
}
if sum == 0 {
stack.push(1);
} else {
stack.push(2 * sum);
}
}
}
stack.iter().sum()
}
}
#[test]
fn test() {
let s = "()".to_string();
let res = 1;
assert_eq!(Solution::score_of_parentheses(s), res);
let s = "(())".to_string();
let res = 2;
assert_eq!(Solution::score_of_parentheses(s), res);
let s = "()()".to_string();
let res = 2;
assert_eq!(Solution::score_of_parentheses(s), res);
let s = "(()(()))".to_string();
let res = 6;
assert_eq!(Solution::score_of_parentheses(s), res);
}
Having problems with this solution? Click here to submit an issue on github.