LeetCode 补充题 109. 使两类括号合法的最少插入次数
题目描述
[!green]
牛客原题： ✅ 补充题 109. 使两类括号合法的最少插入次数
给你一个只包含
(、)、[、]的字符串s，请返回将它变为合法括号序列所需插入的最少括号数。合法序列中的括号必须类型匹配、嵌套顺序正确。你只能插入括号，不能删除原字符或改变原字符的相对顺序。
示例 1：
输入：
s = "([[])"
输出：1
解释： 在最后的右圆括号前插入一个]，得到"([[]])"。
示例 2：
输入：
s = "([)]"
输出：2
解释： 可插入]和[，得到"([])[]"；原有字符的顺序不变。
示例 3：
输入：
s = "()[]"
输出：0
解释： 原字符串已经满足类型匹配和合法嵌套。
提示：
- 字符串只含
(、)、[、]。 - 仅允许插入括号，不允许删除或改变原字符顺序。
- 配对类型及嵌套顺序均需合法。
题意分析
两类括号不仅数量要匹配，类型和嵌套顺序也要正确。只能插入意味着原字符的顺序必须保留，不能通过删除或重排来消除交叉。
最优补全可以按区间拆解：首尾配成一对时处理内部，否则考虑合法部分的拼接。相同子区间会在多种拆法中反复出现，因此用区间动态规划保存最少插入数。
解法：区间 DP 枚举配对与切分
核心思路
[!blue]
这里要优化的是“补成合法括号串的最少插入数”，只用栈判断现有串是否合法还不够。把问题缩小到连续区间：
dp[l][r]表示补全s[l..r]的最小插入数。
- 一个括号缺少自己的另一半，所以
dp[i][i] = 1；空串为 0。- 若两端是同类型的一对，例如
(与)，可以先让它们配对，代价等于内部区间；长度为 2 时内部为空，代价为 0。- 合法串也可能由两段合法串拼接而成。因此枚举切点
m，比较dp[l][m] + dp[m+1][r]。不能只检查首尾，否则会漏掉()[]这种并列结构。按区间长度从短到长计算，内部区间和切开的两段都已经有答案。例如
([)]左右数量虽然平衡，但类型交叉，单纯计数无法决定补全费用；区间状态同时保留了顺序与类型关系。
解题步骤
- 空串直接返回 0，所有单字符区间初始化为 1。
- 按长度递增枚举
[l,r]，先尝试把同类型的左右端括号配成一对。- 枚举每个切点，将左右两段的最少插入数相加，与当前候选取较小值。
- 返回覆盖整串的
dp[0][n-1]。
代码实现
class Solution {
public int minInsertions(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len <= n; l++) {
int r = l + len - 1;
dp[l][r] = n;
char a = s.charAt(l);
char b = s.charAt(r);
if ((a == '(' && b == ')') || (a == '[' && b == ']')) {
dp[l][r] = len == 2 ? 0 : dp[l + 1][r - 1];
}
for (int m = l; m < r; m++) {
dp[l][r] = Math.min(dp[l][r], dp[l][m] + dp[m + 1][r]);
}
}
}
return dp[0][n - 1];
}
}
func minInsertions(s string) int {
n := len(s)
if n == 0 {
return 0
}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
dp[i][i] = 1
}
for length := 2; length <= n; length++ {
for l := 0; l+length <= n; l++ {
r := l + length - 1
dp[l][r] = n
if s[l] == '(' && s[r] == ')' || s[l] == '[' && s[r] == ']' {
if length == 2 {
dp[l][r] = 0
} else {
dp[l][r] = dp[l+1][r-1]
}
}
for m := l; m < r; m++ {
dp[l][r] = min(dp[l][r], dp[l][m]+dp[m+1][r])
}
}
}
return dp[0][n-1]
}
复杂度分析
- 时间复杂度：$O(n^3)$，有 $O(n^2)$ 个区间，每个区间最多枚举 $O(n)$ 个切点。
- 空间复杂度：$O(n^2)$，用于保存全部区间的最优值。
关键点总结
[!green]
一段平衡序列可由外层匹配括号包住内部，或由两段平衡序列拼接，这两类分解覆盖所有合法补全。
易错点总结
[!yellow]
只数左右括号数量无法处理交叉嵌套；不能把方括号和圆括号混配。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1312. 让字符串成为回文串的最少插入次数 | 困难 | 都对字符串区间计算最少插入数，先判断两端能否配对再处理内部；括号还可能由两个独立合法区间拼接，因此本题需增加区间切分转移。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！