leetcode：1249. 移除无效的括号

题目

给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例：

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

输入：s = "a)b(c)d"
输出："ab(c)d"

输入：s = "))(("
输出：""
解释：空字符串也是有效的

解答 & 代码

用栈 leftBracketIdxS 存储左括号的下标，用哈希表 deleteIdxSet 存储需要删除的括号的下标

遍历字符串 s 的每一位 s[i]
1. 如果 s[i] 是左括号，则将下标 i 入栈 leftBracketIdxS
2. 如果 s[i] 是右括号
  1. 如果在它前面存在和它匹配的左括号，即栈 leftBracketIdxS 不为空，则匹配，弹出 leftBracketIdxS 的栈顶
  2. 否则，s[i] 是无效的右括号，将下标 i 存入哈希表 deleteIdxSet
遍历栈 leftBracketIdxS：剩下的这些左括号都没有匹配的右括号，因此都是无效的左括号，将下标存储到哈希表 deleteIdxSet

遍历字符串 s 的每一位 s[i]

如果 i 不在哈希表 deleteIdxSet，则将该位 s[i] 存到结果字符串 result

否则，s[i] 是需要删除的无效括号，跳过

class Solution {
public:
string minRemoveToMakeValid(string s) {
  stack<int> leftBracketIdxS;            // 栈，存储左括号的下标
  unordered_set<int> deleteIdxSet;    // 哈希表，存储无效括号的下标
  int len = s.size();
  // 1. 遍历字符串 s
  for(int i = 0; i < len; ++i)
  {
      if(s[i] == '(')
          leftBracketIdxS.push(i);        // 将左括号的下标入栈
      else if(s[i] == ')')
      {
          if(!leftBracketIdxS.empty())    // 右括号和左括号匹配，弹出栈顶
              leftBracketIdxS.pop();
          else
              deleteIdxSet.insert(i);        // 记录无效右括号的下标
      }
  }
  // 2. 遍历栈中剩余的元素（都是无效左括号的下标）
  while(!leftBracketIdxS.empty())
  {
      deleteIdxSet.insert(leftBracketIdxS.top());    // 记录无效左括号的下标
      leftBracketIdxS.pop();
  }
  // 3. 遍历字符串 s，将有效部分字符存入 result
  string result;
  for(int i = 0; i < len; ++i)
  {
      if(deleteIdxSet.find(i) == deleteIdxSet.end())    // 有效字符
          result.push_back(s[i]);
  }
  return result;
}
};

复杂度分析：设字符串 s 长为 N

时间复杂度 O(N)：
空间复杂度 O(N)：

执行结果：

执行结果：通过
执行用时：24 ms, 在所有 C++ 提交中击败了 49.89% 的用户
内存消耗：11.6 MB, 在所有 C++ 提交中击败了 27.269% 的用户

hot 100

[中等] 1249. 移除无效的括号

题目

解答 & 代码