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 score1.ABhas scoreA + B, whereAandBare balanced parentheses strings.(A)has score2 * A, whereAis 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 <= 50sconsists of only'('and')'.sis 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 complexity | O(n) |
| Space complexity | O(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 complexity | O(n) |
| Space complexity | O(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