LeetCode 题解工作台
使括号有效的最少添加
只有满足下面几点之一，括号字符串才是有效的： 它是一个空字符串，或者 它可以被写成 AB （ A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者 它可以被写作 (A) ，其中 A 是有效字符串。 给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号 例如，如果 …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
这个问题属于经典的括号匹配问题，可以使用“贪心 + 栈”来解决。 遍历字符串 的每个字符 ：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成
AB（A与B连接）, 其中A和B都是有效字符串，或者 - 它可以被写作
(A)，其中A是有效字符串。
给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号
- 例如，如果
s = "()))"，你可以插入一个开始括号为"(()))"或结束括号为"())))"。
返回 为使结果字符串 s 有效而必须添加的最少括号数。
示例 1：
输入：s = "())" 输出：1
示例 2：
输入：s = "((("
输出：3
提示：
1 <= s.length <= 1000s只包含'('和')'字符。
解题思路
方法一：贪心 + 栈
这个问题属于经典的括号匹配问题，可以使用“贪心 + 栈”来解决。
遍历字符串 的每个字符 ：
- 若 为左括号，直接将 入栈；
- 若 为右括号，此时如果栈不为空，且栈顶元素为左括号，则将栈顶元素出栈，表示匹配成功；否则将 入栈。
遍历结束后，栈中剩余的元素个数即为需要添加的括号数。
时间复杂度为 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def minAddToMakeValid(self, s: str) -> int:
stk = []
for c in s:
if c == ')' and stk and stk[-1] == '(':
stk.pop()
else:
stk.append(c)
return len(stk)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) as each character is visited once. Space complexity is O(1) because only counters are maintained instead of an actual stack, making it optimal for large strings. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Check if candidate handles both excess '(' and ')' correctly.
- question_mark
Listen for discussion of O(1) space using counters versus explicit stack.
- question_mark
Evaluate understanding of stack-based state tracking applied greedily.
常见陷阱
外企场景- error
Failing to count unmatched ')' during iteration leading to undercounted insertions.
- error
Using a full stack unnecessarily, increasing space usage.
- error
Ignoring leftover '(' at the end of the string.
进阶变体
外企场景- arrow_right_alt
Compute minimum removals instead of insertions to make a parentheses string valid.
- arrow_right_alt
Apply the same stack-based method to strings containing other types of brackets.
- arrow_right_alt
Return the corrected valid string after minimal insertions rather than just the count.