856.score-of-parentheses.md

856. Score of Parentheses

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Stack

Suppose we have the string: s = (()(())), we can use stack to solve this problem:

1. For (, we just push it into stack.
2. For ), we pop until we encounter (, then we calculate the score of the number between the parentheses and push it back to stack.
   • If the peek of stack is (, then we form () which has score 1.
   • If the peek of stack is a number, then we form (A, B) which has score A + B = C and then pattern (C), so 2 * C.

For example, the process of (()(())) is as follows:

s           action          stack
(           push `(`,       `[(]`       
((          push `(`,       `[(, (]`
(()         pop until `(`,  `[(, 1]`
> it forms `()` which has score 1, then we push 1.
(()(        push `(`,       `[(, 1, (]`
(()((       push `(`,       `[(, 1, (, (]`
(()(()      pop until `(`,  `[(, 1, (, 1]`
> it forms `()`, which has score 1, then we push 1.
(()(())     pop until `(`,  `[(, 1, 2]`
> it forms `(1)`, which is `(A)` pattern that has score `2 * A`, so `2 * 1` and push into stack.
(()(()))    pop until `(`,  `[6]`
> it forms `(1, 2)`, which is `(A, B)` pattern that has score `A + B = C` and then pattern `(C)`, so `2 * 3`

Nice diagram to explain: https://leetcode.cn/problems/score-of-parentheses/solutions/1878748/zhua-wa-mou-si-by-muse-77-hy72/

Similar idea: https://leetcode.cn/problems/score-of-parentheses/solutions/39148/kan-bu-dong-bie-ren-de-ti-jie-zi-ji-you-xie-liao-y/

fun scoreOfParentheses(s: String): Int {
    val stack = Stack<String>()
    for (c in s) {
        // For `(`, we just push it into stack.
        if (c == '(') {
            stack.push(c.toString())
        } else {
            // For `)`, we pop until we encounter `(`, then we calculate the score of `()` and push it back to stack.
            if (stack.peek() == "(") { // For the case "()" in stack
                // Pop the left '('
                stack.pop()
                // Form "()" which has score 1.
                stack.push(1.toString())
            } else {
                // For the case "(A,B,C)" in stack
                var num = 0
                while (stack.isNotEmpty() && stack.peek() != "(") {
                    num += stack.pop().toInt()
                }
                // Pop the left '('
                stack.pop()
                // Form "(A,B,C)" which has score 2 * (A + B + C).
                num *= 2
                stack.push(num.toString())
            }
        }
    }
    // Sum up all scores in stack.
    var result = 0
    while (stack.isNotEmpty()) {
        result += stack.pop().toInt()
    }
    return result
}

• Time Complexity: O(n) to iterate all characters in string.
• Space Complexity: O(n) for stack.

I don't understand the following solution, but it works.

fun scoreOfParentheses(s: String): Int {
    val stack = Stack<Int>()
    var num = 0
    for (c in s) {
        if (c == '(') {
            stack.push(num)
            num = 0
        } else {
            num = stack.pop() + maxOf(1, num * 2)
        }
    }
    return num
}