Skip to content

LeetCode: 856-Score of Parentheses 解題紀錄

Last Updated on 2022-03-17 by Clay

題目

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

  • "()" has score 1.
  • AB has score A + B, where A and B are balanced parentheses strings.
  • (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

Constraints:

  • 2 <= s.length <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.

題目輸入一組字串,字串中只會有 () 兩種字元,而且一定是有效的括號(代表不會出現 )( 這樣的順序)。

一組有效的括號代表分數 1。而括號中如果有其他分數,則是分數乘以 2。比方說 (()) 就是 1*2 = 2((())) 就是 1*2*2 = 4

最後回傳字串所代表的分數。


解題思路

最近解了太多這種括號的題目,看到的第一感就是開始建 stack;然而我使用 stack 的方法來解雖然速度很快,但是空間複雜度居然只少於 5% 的人...... 後來看了討論區,這才發現直接計算括號所在位置的深度是個更好的做法。


Stack 解法

在遍歷字串時,每逢遇到 ( 時便在 stack 中放入代表此符號的數字 0,在遇到 ) 則判斷 stack 的最上層是否是代表 (0;若是,則在 stack 中放入 1,因為一組合法的括號分數為 1。

如果不是 0 的情況,則代表合法的括號之間尚存在其他的分數,在括號中的分數需要全部彈出、加總直到碰到 0 為止,最後再乘以 2,這才會是合法括號所代表的數字。

同時也別忘了,需要再把這個數字放回 stack 中,因為這個分數同樣有可能存在於其他合法括號中。

字串遍歷結束以後,再把 stack 中的所有分數加總。


Stack 解法複雜度

因為使用了 stack 去儲存分數,故空間複雜度為 O(n)。

Time complexityO(n)
Space complexityO(n)


Stack 解法 C++ 範例程式碼

class Solution {
public:
    int scoreOfParentheses(string s) {
        // Init
        int score = 0;
        stack<int> st;
        
        // Traversal
        for (int i=0; i<s.size(); ++i) {
            if (s[i] == '(') {
                st.push(0);
            }
            else {
                int temp = 0;

                // If the top is number
                while (!st.empty() && st.top() != 0) {
                    temp += st.top();
                    st.pop();
                }
                
                // If we finally get the top is '('
                st.pop();
                
                // The number need to times 2, and the lowest one is 1
                temp = max(1, temp*2);
                
                // We need to store the temp value into stack
                st.push(temp);                
            }
        }
        
        // Computation
        while (!st.empty()) {
            score += st.top();
            st.pop();
        }
        
        return score;
    }
};



Stack 解法 Python 範例程式碼

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        # Init
        score = 0;
        st = []
        
        # Traversal
        for c in s:
            if c == '(':
                st.append(0)
            else:
                temp = 0
                
                # If the top is number
                while st and st[-1] != 0:
                    temp += st.pop()

                # If we finally get the top is '('
                st.pop()
                
                # The number need to times 2, and the lowest one is 1
                temp = max(1, temp*2)
                
                # We need to store the temp value into stack
                st.append(temp)              
        
        # Computation
        return sum(st)



計算深度解法

我們可以在每次遇到 ( 時把深度 + 1,在遇到 ) 時把深度 - 1。而唯一需要計算分數時,就是前一個字元剛好為 ( 的情況,所以我宣告了一個 bool 值在遇到 ( 為真、遇到 ) 為假,這樣一來就可以在前一字元為 ( 時使用深度計算分數。

比方說 (()) 我們只有在碰到第一個 ) 時才會計算,而此時的深度為 1,分數的計算公式是 2^1=2

比方說 ((())) 我們同樣是在碰到第一個 ) 時才會計算,而此時的深度為 2,分數的計算公式為 2^2=4

(()()) 我們則會計算兩次,而深度都為 1,故分數為 2^1 + 2^1 = 4

這個方法不需要建立 stack,不論是時間還是空間複雜度都更低,是適當的解法。


計算深度複雜度

Time complexityO(n)
Space complexityO(1)


計算深度解法 C++ 範例程式碼

class Solution {
public:
    int scoreOfParentheses(string s) {
        // Init
        int depth = 0;
        int score = 0;
        bool needCount = false;
        
        // Traversal
        for (auto& c: s) {
            if (c == '(') {
                ++depth;
                needCount = true;
            }
            else {
                --depth;
                
                if (needCount) {
                    score += pow(2, depth);
                }
                
                needCount = false;
            }            
        }
        
        return score;
    }
};



計算深度解法 Python 範例程式碼

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        # Init
        depth = 0
        score = 0
        needCount = False
        
        # Traversal
        for c in s:
            if c == '(':
                depth += 1
                needCount = True
            else:
                depth -= 1
                
                if needCount:
                    score += pow(2, depth)
                
                needCount = False  
        
        return score

References


Read More

Leave a Reply