解决LeetCode“使括号有效的最少添加”问题

目录

问题描述

解题思路

复杂度分析

示例分析

暴力替换“不讲码德”

总结

问题描述

给定一个仅由 '(' 和 ')' 组成的字符串 s，我们需要通过添加最少数量的括号（'(' 或 ')'）使得字符串有效。有效字符串需满足：

1. 空字符串是有效的。

2. 如果字符串 A 有效，则 (A) 也有效。

3. 如果字符串 A 和 B 有效，则 AB 也有效。

示例：

• 输入：s = "())" → 输出：1（添加一个 '(' 变成 "()()"）

• 输入：s = "(((" → 输出：3（添加三个 ')'）

解题思路

核心思想是每一步尽可能匹配括号，以减少后续需要添加的数量：

1. 左括号计数：遍历字符串时记录未匹配的左括号数量。

2. 处理右括号：遇到右括号时，优先匹配最近的左括号。若没有可匹配的左括号，则需添加一个左括号。

3. 剩余左括号：遍历结束后，未匹配的左括号每个都需要一个右括号。

这种贪心策略确保每一步都最大化有效括号的数量，从而最小化添加次数。

var minAddToMakeValid = function(s) {
    let ans = 0;         // 需要添加的括号总数
    let leftCount = 0;   // 当前未匹配的左括号数量
    const length = s.length;

    for (let i = 0; i < length; i++) {
        const c = s[i];
        if (c === '(') {
            leftCount++; // 遇到左括号，计数增加
        } else {
            if (leftCount > 0) {
                leftCount--; // 有左括号可匹配，计数减少
            } else {
                ans++;       // 无左括号可匹配，需添加一个左括号
            }
        }
    }
    ans += leftCount;    // 剩余未匹配的左括号需添加对应右括号
    return ans;
};

复杂度分析

• 时间复杂度：O(n)，只需遍历一次字符串。

• 空间复杂度：O(1)，仅使用常数级别的额外空间。

示例分析

以输入 s = "())" 为例：

1. 遍历字符 '(' → leftCount = 1。

2. 字符 ')' → leftCount = 0。

3. 字符 ')' → 无左括号可匹配，ans = 1。

4. 结束遍历，剩余 leftCount = 0，总结果 ans = 1。

暴力替换“不讲码德”
 

var minAddToMakeValid = function(s) {
    while(s.includes("()")) { // 循环替换所有 "()"
        s = s.replace("()", "");
    }
    return s.length; // 剩余字符长度即为答案
};

“暴力替换”写法存在以下问题：

1. 匹配顺序依赖：结果受 replace() 替换顺序影响，可能错误处理嵌套结构。

2. 结果不稳定：特定结构下碰巧正确，但无法覆盖所有测试用例。

3. 性能隐患：多次字符串替换操作的时间复杂度为 O(n²)，远高于贪心算法的 O(n)。

总结

通过贪心策略，优先匹配最近的左括号，确保每一步都最优，最终得到最少添加次数。此方法高效且简洁，适合处理类似括号匹配问题。