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
.AB
has scoreA + B
, whereA
andB
are balanced parentheses strings.(A)
has score2 * A
, whereA
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 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