Medium

题目描述

给你一个由 ‘(’、’)’ 和小写英文字母组成的字符串 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 <= 10^5
  • s[i] 为 ‘(’ 、’)’ 或小写英文字母

解题思路

这个问题需要删除最少的括号使得剩余括号匹配。我们可以用两种方法解决：

方法一：两次遍历法（推荐）

核心思想是分两步：

  1. 从左到右遍历：统计多余的右括号 ‘)’，这些右括号没有对应的左括号来匹配，需要删除
  2. 从右到左遍历：统计多余的左括号 ‘(’，这些左括号没有对应的右括号来匹配，需要删除

具体过程：

  • 第一次遍历维护一个计数器，遇到 ‘(’ 就+1，遇到 ‘)’ 就-1，当计数器为负数时说明右括号过多，标记删除
  • 第二次遍历同样维护计数器，但从右往左，遇到 ‘)’ 就+1，遇到 ‘(’ 就-1，当计数器为负数时说明左括号过多，标记删除

方法二：栈法

使用栈存储左括号的索引，遍历字符串时：

  • 遇到左括号入栈
  • 遇到右括号时，如果栈不为空则弹出匹配的左括号，否则标记该右括号为无效
  • 最后栈中剩余的左括号索引都是无效的

两种方法时间复杂度相同，但两次遍历法空间复杂度更优。

代码实现

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string result;
        int balance = 0;
        
        // 第一次遍历：从左到右，移除多余的右括号
        for (char c : s) {
            if (c == '(') {
                balance++;
                result += c;
            } else if (c == ')' && balance > 0) {
                balance--;
                result += c;
            } else if (c != ')') {
                result += c;
            }
        }
        
        // 第二次遍历：从右到左，移除多余的左括号
        string finalResult;
        balance = 0;
        for (int i = result.length() - 1; i >= 0; i--) {
            char c = result[i];
            if (c == ')') {
                balance++;
                finalResult += c;
            } else if (c == '(' && balance > 0) {
                balance--;
                finalResult += c;
            } else if (c != '(') {
                finalResult += c;
            }
        }
        
        reverse(finalResult.begin(), finalResult.end());
        return finalResult;
    }
};

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        # 第一次遍历：从左到右，移除多余的右括号
        result = []
        balance = 0
        
        for c in s:
            if c == '(':
                balance += 1
                result.append(c)
            elif c == ')' and balance > 0:
                balance -= 1
                result.append(c)
            elif c != ')':
                result.append(c)
        
        # 第二次遍历：从右到左，移除多余的左括号
        final_result = []
        balance = 0
        
        for c in reversed(result):
            if c == ')':
                balance += 1
                final_result.append(c)
            elif c == '(' and balance > 0:
                balance -= 1
                final_result.append(c)
            elif c != '(':
                final_result.append(c)
        
        return ''.join(reversed(final_result))

public class Solution {
    public string MinRemoveToMakeValid(string s) {
        StringBuilder result = new StringBuilder();
        int balance = 0;
        
        // 第一次遍历：从左到右，移除多余的右括号
        foreach (char c in s) {
            if (c == '(') {
                balance++;
                result.Append(c);
            } else if (c == ')' && balance > 0) {
                balance--;
                result.Append(c);
            } else if (c != ')') {
                result.Append(c);
            }
        }
        
        // 第二次遍历：从右到左，移除多余的左括号
        StringBuilder finalResult = new StringBuilder();
        balance = 0;
        for (int i = result.Length - 1; i >= 0; i--) {
            char c = result[i];
            if (c == ')') {
                balance++;
                finalResult.Append(c);
            } else if (c == '(' && balance > 0) {
                balance--;
                finalResult.Append(c);
            } else if (c != '(') {
                finalResult.Append(c);
            }
        }
        
        char[] chars = finalResult.ToString().ToCharArray();
        Array.Reverse(chars);
        return new string(chars);
    }
}

var minRemoveToMakeValid = function(s) {
    let openCount = 0;
    let result = [];
    
    // First pass: remove invalid closing parentheses
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            openCount++;
            result.push(s[i]);
        } else if (s[i] === ')') {
            if (openCount > 0) {
                openCount--;
                result.push(s[i]);
            }
        } else {
            result.push(s[i]);
        }
    }
    
    // Second pass: remove extra opening parentheses from right to left
    let finalResult = [];
    let extraOpen = openCount;
    
    for (let i = result.length - 1; i >= 0; i--) {
        if (result[i] === '(' && extraOpen > 0) {
            extraOpen--;
        } else {
            finalResult.push(result[i]);
        }
    }
    
    return finalResult.reverse().join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串的长度。需要两次遍历字符串，每次都是 O(n)，所以总时间复杂度为 O(n)。空间复杂度为 O(n)，主要用于存储结果字符串。

相关题目