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(Aconcatenated withB), whereAandBare valid strings, or - It can be written as(A), whereAis 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 <= 105s[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