LeetCode 题解工作台
移除无效的括号
给你一个由 '(' 、 ')' 和小写字母组成的字符串 s 。 你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下 任意一条 要求： 空字符串或只包含小写字母的字符串 可以被写作…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们先从左向右扫描，将多余的右括号删除，再从右向左扫描，将多余的左括号删除。 时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
- 空字符串或只包含小写字母的字符串
- 可以被写作
AB（A连接B）的字符串，其中A和B都是有效「括号字符串」 - 可以被写作
(A)的字符串，其中A是一个有效的「括号字符串」
示例 1：
输入：s = "lee(t(c)o)de)" 输出："lee(t(c)o)de" 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
示例 2：
输入：s = "a)b(c)d" 输出："ab(c)d"
示例 3：
输入：s = "))(("
输出：""
解释：空字符串也是有效的
提示：
1 <= s.length <= 105s[i]可能是'('、')'或英文小写字母
解题思路
方法一：两遍扫描
我们先从左向右扫描，将多余的右括号删除，再从右向左扫描，将多余的左括号删除。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
相似题目：
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stk = []
x = 0
for c in s:
if c == ')' and x == 0:
continue
if c == '(':
x += 1
elif c == ')':
x -= 1
stk.append(c)
x = 0
ans = []
for c in stk[::-1]:
if c == '(' and x == 0:
continue
if c == ')':
x += 1
elif c == '(':
x -= 1
ans.append(c)
return ''.join(ans[::-1])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask if you can perform removals in-place versus constructing a new string.
- question_mark
Check understanding of prefix balance: no prefix has more ')' than '(' during the first pass.
- question_mark
Probe how the solution scales when nearly all characters are parentheses.
常见陷阱
外企场景- error
Forgetting to remove unmatched '(' left in the stack after processing all characters.
- error
Assuming the first invalid ')' encountered can be paired later instead of skipped immediately.
- error
Overcomplicating reconstruction by repeated string concatenation instead of using a list or buffer.
进阶变体
外企场景- arrow_right_alt
Return all possible valid strings with minimum removals instead of just one.
- arrow_right_alt
Count the minimum number of removals required without returning the actual string.
- arrow_right_alt
Apply the same removal logic to multiple types of brackets like '{}', '[]' in addition to '()'.