VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 1249. 移除无效的括号

Posted on Edited on In , ,

摘要：
华为面试题，时间不够没写出来，面试结束补上了，还是我太菜了。

题目

给你一个由 '(' 、')' 和小写字母组成的字符串 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 = “))((“
输出：””
解释：空字符串也是有效的

示例 4：

输入：s = “(a(b(c)d)”
输出：”a(b(c)d)”

提示：

  • $ 1 <= s.length <= 10^5$
  • s[i] 可能是 '(' 、')' 或英文小写字母

栈

维护一个栈，将所有有效括号对去除，剩下的就是字符串中多余的目标括号。为了将字符串中多余的括号去除，需要在栈中记录括号对应原字符串下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    const static int N = 100010;
    pair<char, int> stk[N];
    int tt = 0;

    string minRemoveToMakeValid(string s) {
        string res = "";
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];

            if (c == '(' || c == ')') {
                if (c == '(') stk[++tt] = {c, i};
                else {
                    if (!tt || stk[tt].first != '(') stk[++tt] = {c, i};
                    else --tt;
                }
            }
        }

        if (!tt) return s;
        if (tt) {
            for (int i = s.size() - 1; i >= 0; i--) {
                if (tt && i == stk[tt].second) {
                    --tt;
                    continue;
                }
                else res += s[i];
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

原题链接： LeetCode 1249. 移除无效的括号