Last Updated on 2022-03-15 by Clay
題目
Given a string s of'('
,')'
and lowercase English characters. Your task is to remove the minimum number of parentheses ('('
or')'
, in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if and only if: - It is the empty string, contains only lowercase characters, or - It can be written asAB
(A
concatenated withB
), whereA
andB
are valid strings, or - It can be written as(A)
, whereA
is a valid string.
Example 1:
Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:
Input: s = "a)b(c)d" Output: "ab(c)d"
Example 3:
Input: s = "))((" Output: "" Explanation: An empty string is also valid.
Constraints:
1 <= s.length <= 105
s[i]
is either'('
,')'
, or lowercase English letter.
題目輸入一組字串,字串中除了小寫的英文字母外還包含著『括號』。括號很有可能是無效的括號,比方說 )(
就是一組無效的括號。括號需要是左右各一對,並且中間允許存在其他字元。
而我們要做的,就是把無效的括號刪除,直到整個字串只留下有效的括號。以 Example 1 來說:
lee(t(c)o)de)
存在著 2 個左括號和 3 個右括號,我們要需要把其中一個右括號刪去,該字串才僅存在有效的括號。
解題思路
Stack
以往每次碰到判斷左右括號是否有效的問題,我第一時間都會嘗試使用 stack 的結構來解題。在 stack 中不存在任何元素時碰到 )
即判斷無效,如果容器的最上頭是 (
則判斷是有效的括號。
因為這題需要將無效的括號刪除,於是我的 stack 容器中儲存著無效括號的位置,只要沒有彈出,最後我通通都將無效括號的位置刪除。(我使用 *
來代表無效字元,最後直接刪除掉 *
)
不過老實說,無論是 C++ 還是 Python,在這題上使用兩端點各跑一次然後遮蔽無效括號都更快(可以參考下方另外一種解法)。尤其是 Python,我在 LeetCode 上提交了幾次測試,快了快要十倍左右。
或許 Python 還有什麼巧妙的解法也說不定?但我主要都是拿 C++ 在練習,或許真的生疏了 Python 的程式技巧。
Stack 複雜度
因為使用了 stack 儲存位置資訊,故空間複雜度應為 O(n)。
Time complexity | O(n) |
Space complexity | O(n) |
Stack C++ 範例程式碼
class Solution {
public:
string minRemoveToMakeValid(string s) {
// Init
stack<int> pos;
// Make valid
for (int i=0; i<s.size(); ++i) {
if (s[i] == '(') {
pos.push(i);
}
else if (s[i] == ')') {
if (pos.empty() || s[pos.top()] != '(') {
pos.push(i);
}
else {
pos.pop();
}
}
}
// Mask
for (int i=s.size()-1; i>=0; --i) {
if (!pos.empty() && i == pos.top()) {
s[i] = '*';
pos.pop();
}
}
// Remove all '*' symbols
s.erase(std::remove(s.begin(), s.end(), '*'), s.end());
return s;
}
};
Stack Python 範例程式碼
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
# Init
stack = []
# Find invalid
for i in range(len(s)):
if s[i] == ')':
if len(stack) == 0 or s[stack[-1]] != '(':
stack.append(i)
else:
stack.pop()
elif s[i] == '(':
stack.append(i)
# Mask
s = ''.join([s[i] for i in range(len(s)) if i not in stack])
return s
兩端點解法
這是我認為更好的解法,時間跟空間都節省了不少。
簡單來說,如果我們單純將字串從左掃到右,其實我們完全可以判斷出哪些 )
是多餘、無效的。只需要一個 count
變數計算左括號的可匹配數量即可:
) a ( b ( c ) d ) e ) ) : count=0,無效,無可匹配的左括號 ( a : 字母跳過 ( : count=1 b : 字母跳過 ( : count=2 c : 字母跳過 ) : count-1=1, 有效,有可匹配的左括號 ( d : 字母跳過 ) : count-1=0,有效,有可匹配的左括號 ( e : 字母跳過 ) : count=0,無效,無可匹配的左括號 ( 把跳過的字母拿掉,看得更清楚: ) : count=0,無效,無可匹配的左括號 ( ( : count=1 ( : count=2 ) : count-1=1, 有效,有可匹配的左括號 ( ) : count-1=0,有效,有可匹配的左括號 ( ) : count=0,無效,無可匹配的左括號 (
反過來說,如果我們從右邊開始匹配,則我們可以判斷出哪些左括號 (
是無效的!
於是左右各做一次,我們就能抓出所有無效的括號了。
兩端點複雜度
只需要 count
變數儲存次數即可,故空間複雜度 O(1)。(Python 則不確定記憶體存取情況......)
Time complexity | O(n) |
Space complexity | O(1) |
兩端點 C++ 範例程式碼
class Solution {
public:
string minRemoveToMakeValid(string s) {
// Init
int count = 0;
// Left to right
for (int i=0; i<s.size(); ++i) {
if (s[i] == '(') ++count;
else if (s[i] == ')') {
if (count) --count;
else s[i] = '*';
}
}
// Right to left
count = 0;
for (int i=s.size()-1; i>=0; --i) {
if (s[i] == ')') ++ count;
else if (s[i] == '(') {
if (count) --count;
else s[i] = '*';
}
}
// Remove all '*' symbols
s.erase(std::remove(s.begin(), s.end(), '*'), s.end());
return s;
}
};
Stack Python 範例程式碼
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
# Init
s = list(s)
count = 0
# Left to right
for i in range(len(s)):
if s[i] == '(':
count += 1
elif s[i] == ')':
if count > 0:
count -= 1
else:
s[i] = ''
# Right to left
count = 0
for i in range(len(s)-1, -1, -1):
if s[i] == ')':
count += 1
elif s[i] == '(':
if count > 0:
count -= 1
else:
s[i] = ''
# Mask
s = ''.join(s)
return s