日期：2026年10月7日
LeetCode 題目連結：301. Remove Invalid Parentheses
解題想法
困難題。題目給一個字串 $s$，$s$ 之中只有 $(, )$ 及小寫英文字母，如果要將 $s$ 變成合法的括號字串，最少要移除幾個括號？
這題下方有提示要用遞迴窮舉所有可能的組合。我一開始的寫法，先計算 $s$ 之中要移除的括號總數。用串列 $path$ 記錄目前已選的字元，用集合 $ans$ 儲存答案，並且定義在自訂函式 $dfs$ 之前。呼叫 $dfs$ 時代入 $idx, removed, balance$，代表正在檢查 $s[idx]$，已經移除 $removed$ 個括號，目前左括號比右括號多 $balance$ 個。如果 $idx == n$ 且 $balance == 0$，找到一組解，將 $path$ 接成字串加入 $ans$。這個寫法雖然可以過關，但是效率並不好。
後來改成計算 $s$ 之中要移除的左、右括號 $left, right$。呼叫 $dfs$ 時代入 $idx, le, ri, balance$，代表正在檢查 $s[idx]$，待移除的左括號數量 $le$，待移除的右括號數量 $ri$，目前左括號比右括號多 $balance$ 個。如果 $idx == n$ 且 $balance == 0$，找到一組解，將 $path$ 接成字串加入 $ans$。加上剪枝條件，如果剩下的部分全刪也無法消耗剩下的 $le + ri$。窮舉時先檢查是否還能移除這個括號或是可以加入這個括號才遞迴。這個寫法的效率比上一個寫法好很多。
Python 程式碼
Runtime: 1358 ms, beats 16.73%. Memory: 19.49 MB, beats 80.04%.
class Solution:
def removeInvalidParentheses(self, s: str) -> list[str]:
# 1. 計算要移除的括號數量
target, left = 0, 0 # 要移除的括號數量，待配對的 (
for c in s:
if c == '(':
left += 1
elif c == ')':
if left > 0: left -= 1
else: target += 1
target += left # 加上剩下的 (
# 定義窮舉用的 dfs 函式
n = len(s) # 長度
ans = set() # 答案
path = [] # 已選的字元
def dfs(idx, removed, balance):
# 正在檢查 s[idx]，已經移除的數量，左、右括數量差
if idx == n: # 遞迴出口
# 括號成對，移除數量等於目標值，找到一組答案
if balance == 0 and removed == target:
ans.add("".join(path))
return
# 窮舉
if s[idx] == '(': # 左括號
path.append('(')
dfs(idx + 1, removed, balance + 1) # 遞迴
path.pop() # 回溯
if removed < target: # 不選 s[idx]
dfs(idx + 1, removed + 1, balance) # 遞迴
elif s[idx] == ')': # 右括號
if balance > 0: # 可以加入右括號
path.append(')')
dfs(idx + 1, removed, balance - 1) # 遞迴
path.pop() # 回溯
if removed < target: # 不選 s[idx]
dfs(idx + 1, removed + 1, balance) # 遞迴
else: # 字母
path.append(s[idx])
dfs(idx + 1, removed, balance) # 遞迴
path.pop() # 回溯
dfs(0, 0, 0)
return list(ans)
Runtime: 153 ms, beats 41.04%. Memory: 19.30 MB, beats 99.02%.
class Solution:
def removeInvalidParentheses(self, s: str) -> list[str]:
# 1. 計算要移除的左、右括號數量
left, right = 0, 0 # 待配對的括號數量
for c in s:
if c == '(':
left += 1
elif c == ')':
if left > 0: left -= 1
else: right += 1
# 定義窮舉用的 dfs 函式
n = len(s) # 長度
ans = set() # 答案
path = [] # 已選的字元
def dfs(idx, le, ri, balance):
# 正在檢查 s[idx]，剩下要移除的數量，左、右括數量，括號數量差
if idx == n: # 遞迴出口
# 括號成對，找到一組答案
if le == 0 and ri == 0 and balance == 0:
ans.add("".join(path))
return
# 剪枝，剩下的字元全部不選也不夠消耗剩下要移除的括號
if n - idx < le + ri:
return
# 窮舉
if s[idx] == '(': # 左括號
path.append('(')
dfs(idx + 1, le, ri, balance + 1) # 遞迴
path.pop() # 回溯
if le > 0: # 不選 (
dfs(idx + 1, le - 1, ri, balance) # 遞迴
elif s[idx] == ')': # 右括號
if balance > 0: # 可以加入右括號
path.append(')')
dfs(idx + 1, le, ri, balance - 1) # 遞迴
path.pop() # 回溯
if ri > 0: # 不選 )
dfs(idx + 1, le, ri - 1, balance) # 遞迴
else: # 字母
path.append(s[idx])
dfs(idx + 1, le, ri, balance) # 遞迴
path.pop() # 回溯
dfs(0, left, right, 0)
return list(ans)
C++ 程式碼
Runtime: 152 ms, beats 31.65%. Memory: 11.40 MB, beats 85.80%.
class Solution {
public:
int n, target; // 長度，要移除的括號數量
string path; // 已選的字元
unordered_set<string> ans; // 答案
void dfs(const string& s, int idx, int removed, int balance) {
// 正在檢查 s[idx]，已經移除的數量，左、右括數量差
if (idx == n) { // 遞迴出口
// 括號成對，移除數量等於目標值，找到一組答案
if (balance == 0 && removed == target) {
ans.insert(path);
}
return;
}
// 窮舉
if (s[idx] == '(') { // 左括號
path += "(";
dfs(s, idx + 1, removed, balance + 1); // 遞迴
path.pop_back(); // 回溯
if (removed < target) { // 不選 s[idx]
dfs(s, idx + 1, removed + 1, balance); // 遞迴
}
} else if (s[idx] == ')') { // 右括號
if (balance > 0) { // 可以加入右括號
path += ")";
dfs(s, idx + 1, removed, balance - 1); // 遞迴
path.pop_back(); // 回溯
}
if (removed < target) { // 不選 s[idx]
dfs(s, idx + 1, removed + 1, balance); // 遞迴
}
} else { // 字母
path += s[idx];
dfs(s, idx + 1, removed, balance); // 遞迴
path.pop_back(); // 回溯
}
}
vector<string> removeInvalidParentheses(string s) {
// 1. 計算要移除的括號數量
target; // 要移除的括號數量
int left = 0; // 待配對的 (
for(char c : s) {
if (c == '(') {
left++;
} else if (c == ')') {
if (left > 0) left--;
else target++;
}
}
target += left; // 加上剩下的 (
// 2. 用遞迴窮舉所有的答案
n = (int)s.size();
ans.clear();
path.clear();
dfs(s, 0, 0, 0);
vector<string> res (ans.cbegin(), ans.cend());
return res;
}
};
Runtime: 19 ms, beats 79.49%. Memory: 11.36 MB, beats 85.80%.
class Solution {
public:
int n; // 長度
string path; // 已選的字元
unordered_set<string> ans; // 答案
void dfs(const string& s, int idx, int le, int ri, int balance) {
// 正在檢查 s[idx]，待移除的左、右括號數量，左、右括數量差
if (idx == n) { // 遞迴出口
// 括號成對，移除數量等於目標值，找到一組答案
if (balance == 0 && le == 0 && ri == 0) {
ans.insert(path);
}
return;
}
// 剪枝，如果剩下的部分全刪也無法消耗剩下的 le + ri
if (n - idx < le + ri) {
return;
}
// 窮舉
if (s[idx] == '(') { // 左括號
path += "(";
dfs(s, idx + 1, le, ri, balance + 1); // 遞迴
path.pop_back(); // 回溯
if (le > 0) { // 不選 s[idx]
dfs(s, idx + 1, le - 1, ri, balance); // 遞迴
}
} else if (s[idx] == ')') { // 右括號
if (balance > 0) { // 可以加入右括號
path += ")";
dfs(s, idx + 1, le, ri, balance - 1); // 遞迴
path.pop_back(); // 回溯
}
if (ri > 0) { // 不選 s[idx]
dfs(s, idx + 1, le, ri - 1, balance); // 遞迴
}
} else { // 字母
path += s[idx];
dfs(s, idx + 1, le, ri, balance); // 遞迴
path.pop_back(); // 回溯
}
}
vector<string> removeInvalidParentheses(string s) {
// 1. 計算要移除的括號數量
int left = 0, right = 0; // 要刪除的左、右括號數量
for(char c : s) {
if (c == '(') {
left++;
} else if (c == ')') {
if (left > 0) left--;
else right++;
}
}
// 2. 用遞迴窮舉所有的答案
n = (int)s.size();
ans.clear();
path.clear();
dfs(s, 0, left, right, 0);
vector<string> res (ans.cbegin(), ans.cend());
return res;
}
};
沒有留言:
張貼留言