[LeetCode] 856. Score of Parentheses 刷題筆記
Cathy P
 2022-03-25 23:56:18      

題目

LeetCode 連結：
https://leetcode.com/problems/score-of-parentheses/

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.

題目會給一個有效的括號字串，代表不會出現)(或是(()這種左右不對等的括號，而我們要將括號依照題目的規則轉換成分數。
轉換的規則是：

  1. () = 1
  2. 並排的括號會是「相加」的關係
  3. 括號包住括號會是「乘以 2」的關係

Example

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

Example 2:

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

Example 3:

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

解題過程

Stack 解法

  1. 每當遇到(時，就在 stack 上 push0
  2. 遇到)則去判斷 stack 的最上層是否是0
    2-1. 若是0則代表這邊是一個()的情況，()代表數值1，因此我們把 stack 中的0 pop 出來，push1進去。
    2-2. 若不是0代表這組括號之間還有其他的數值，要先把括號裡面的數值加總之後，再將它乘以2。
  3. 最後 stack 裡面會剩下並排關係括號數值，再把 stack 裡面的數值全部相加即是答案

實例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: (()())()

Step1: stack[0]     //遇到左括號，stack放入0
Step2: stack[0,0]   //遇到左括號，stack放入0
Step3: stack[0,1]   //遇到右括號，與左括號合併成1放回stack
Step4: stack[0,1,0] //遇到左括號，stack放入0
Step5: stack[0,1,1] //遇到右括號，與左括號合併成1放回stack
Step6: stack[4]     //遇到右括號，stack最上方不是0(左括號)
                    //先把0(左括號)上面的數值相加之後乘以2
Step7: stack[4,0]   //遇到左括號，stack放入0
Step8: stack[4,1]   //遇到右括號，與左括號合併成1放回
Step9: return 4+1   //將stack的數值相加後回傳

程式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
  let stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            stack.push(0);
        }
        else {
            let score = 0;
            while (stack[stack.length - 1] !== 0) {
                score += stack.pop();
            }
            stack.pop();

            // 如果score=0，代表是()回傳1
            // 如果score!=0，代表要將()中間的數值乘以2
            // 所以直接取(score * 2, 1)的最大值就好
            score = Math.max(score * 2, 1);
            stack.push(score);
        }
    }
    let score = 0;
    while (stack.length > 0) {
        score += stack.pop();
    }
    ;
    return score;
};

而這個的 2-2 將()中間的值相加的這個步驟，可以不用再額外跑一個迴圈，直接在過程中，將數值額外存成一個 tmpScore，只在遇到左括號時將 tmpScore 放入 stack 後歸零。

實例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Input: (()())()

Step1: stack[0]     //遇到左括號，stack放入0
       tmpScore = 0

Step2: stack[0,0]   //遇到左括號，stack放入0
       tmpScore = 0

Step3: stack[0]     //遇到右括號，與左括號合併成1存成tmpScore
       tmpScore = 1

Step4: stack[0,1]   //遇到左括號，stack放入tmpScore的值
       tmpScore = 0 //並將tmpScore歸零

Step5: stack[0]     //遇到右括號合成一個1，與並排的數值1相加=2
       tmpScore = 2 //將2存到tmpScore

Step6: stack[]     //遇到右括號，tmpScore不是0，代表上一個字不是左括號
       tmpScore = 4 //把tmpScore的數值乘以2

Step7: stack[4]     //遇到左括號，stack放入tmpScore的值
       tmpScore = 0 //將tmpScore歸零

Step8: stack[]   //遇到右括號合成一個1，再與並排的數值1相加=5
       tmpScore = 5 //將tmpScore歸零

Step9: return tmpScore

程式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
    let stack = [];
    let tmpScore = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            stack.push(tmpScore);
            tmpScore = 0;
        }
        else {
            tmpScore = stack.pop() + Math.max(tmpScore*2, 1);
        }
    }
    return  tmpScore;
};

複雜度

時間複雜度：O(N)
空間複雜度：O(N)

遞迴解法

看了討論區的文章之後，發現還有遞迴的解法，又用了遞迴的解法嘗試解了一次。

因為()和 function 的()太像了，我把實例演示題目的 input 括號改成中括號[];

function Score()
case 1: Score([]) 回傳 1
case 2: Score([A]) 回傳 Score(A)*2
case 3: Score(AB) 回傳 Score(A)+Score(B)

實例演示：

1
2
3
4
5
6
7
8
Input: [[][]][]

Step1: Score([[][]][])
Step2: Score(Score([[][]])+Score([]))
Step3: Score(Score([Score([])+Score([])])+1)
Step4: Score(Score([1+1])+1)
Step5: Score(2*(1+1)+1)
Step5: = 5

程式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
    return score(s, 0, s.length-1);
};

function score(s, start, end){
  if(start+1 === end){
    return 1;
  }

  let b = 0, cur = 0;
  for(let i=start; i<=end; i++){
    if(s[i]==="("){
      b++;
    }
    else{
      b--;
    }
    if(b === 0){
      if(i!==end || start+1===end){
        cur += score(s, start, i)
        start = i+1;
      }
      else{
        cur += score(s, start+1, end-1)*2;
      }
    }
  }
  return cur;
}

複雜度

時間複雜度：O(N^2)

()()()…情況時複雜度最低：$O(N)$
(((…)))情況時複雜度最高：$O(N^2)$

空間複雜度：$O(N)$

計算深度解法

討論區中，我看到最讓我震驚的解法就是直接計算深度的解法。
這是利用四則運算「分配律」的邏輯解的。

實例演示：

1
Input: (()())()

無論是 stack 還是遞迴的解法，解題的邏輯都是將(()())()轉換成：

1
2*(1+1)+1

而計算深度的解法則是將2*(1+1)+1透過分配律轉換成：

1
2*1 + 2*1 + 1

因此我們只需判斷每一組()的深度是多少，就知道要乘以2*[深度]倍，就能夠得出答案。

程式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
    let b = 0;
    let ans = 0;
    for(let i=0; i<s.length; i++){
        if(s[i] === "("){
            b++;
        }
        else{
            b--;
            if(s[i-1] === "("){
                ans += 1 << b;
            }
        }
    }
    return ans;
};

複雜度

時間複雜度：O(N)
空間複雜度：O(1)

心得

這個問題一開始會想用 stack 解法是因為覺得題目跟四則運算的類型有點像，就直覺用了以前學過的 stack 方法來處理左右括號的問題。
寫完之後參考了其他人的解法做了優化版的 stack 方法。

之後再嘗試用遞迴，最後最最震驚的是，前面兩種做法我一直都被題目框架框住，沒想到這個題目可以先套用分配律將它們拆開計算。

這次的題目對我來說有點難，stack 和遞迴的兩種方式在想演算法跟實際寫程式時都花了一點時間思考，之後又學習了計算深度的解法，這個題目算是收穫滿滿。

另外，我發現 LeetCode 上 Runtime 好像怪怪的，同一個程式碼送出兩次的時間會差很多，上網查發現好像是 LeetCode 上 js 的 Runtime 計算會有問題。所以之後的文章都拿掉這個區塊，改成紀錄時間複雜度與空間複雜度。