leetcode：1249. 移除无效的括号

题目

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

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

示例：

  1. 输入：s = "lee(t(c)o)de)"
  2. 输出："lee(t(c)o)de"
  3. 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
  1. 输入：s = "a)b(c)d"
  2. 输出："ab(c)d"
  1. 输入：s = "))(("
  2. 输出：""
  3. 解释：空字符串也是有效的

解答 & 代码

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

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

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

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

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

      1. class Solution {
      2. public:
      3. string minRemoveToMakeValid(string s) {
      4.   stack<int> leftBracketIdxS;            // 栈，存储左括号的下标
      5.   unordered_set<int> deleteIdxSet;    // 哈希表，存储无效括号的下标
      6.   int len = s.size();
      7.   // 1. 遍历字符串 s
      8.   for(int i = 0; i < len; ++i)
      9.   {
      10.       if(s[i] == '(')
      11.           leftBracketIdxS.push(i);        // 将左括号的下标入栈
      12.       else if(s[i] == ')')
      13.       {
      14.           if(!leftBracketIdxS.empty())    // 右括号和左括号匹配，弹出栈顶
      15.               leftBracketIdxS.pop();
      16.           else
      17.               deleteIdxSet.insert(i);        // 记录无效右括号的下标
      18.       }
      19.   }
      20.   // 2. 遍历栈中剩余的元素（都是无效左括号的下标）
      21.   while(!leftBracketIdxS.empty())
      22.   {
      23.       deleteIdxSet.insert(leftBracketIdxS.top());    // 记录无效左括号的下标
      24.       leftBracketIdxS.pop();
      25.   }
      27.   // 3. 遍历字符串 s，将有效部分字符存入 result
      28.   string result;
      29.   for(int i = 0; i < len; ++i)
      30.   {
      31.       if(deleteIdxSet.find(i) == deleteIdxSet.end())    // 有效字符
      32.           result.push_back(s[i]);
      33.   }
      34.   return result;
      35. }
      36. };

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

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

执行结果：

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