LEETCODE 1249. Minimum Remove to Make Valid Parentheses 解题思路分析

题目大意：

移除无效的括号

给你一个由 '('、')' 和小写字母组成的字符串 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] 可能是 '('、')' 或英文小写字母

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1249

解题思路分析：

题目要求删除无效的括号，所谓有效的括号一定是正括号加上反括号按顺序成对出现，关于有效括号的题目之前做过很多，关键思路是循环字符串，使用Stack来保存已经出现的正括号，当遇见反括号时，查看Stack中是否含有正括号，如果有，就从Stack中pop出一个，保证与当前反括号配对。如果没有，说明当前反括号是多余的，需要被删除。循环结束后，如果Stack中还有剩余的正括号，说明这些也是多余的，应该被删除。未被删除的部分即是答案。

写代码时，我们定义一个boolean数组，记录哪些位置是需要删除的，再定义一个Stack，用来保存出现过的正括号的下标。

实现代码：

public String minRemoveToMakeValid(String s) {
    // 应被删除的位
    boolean[] wrong = new boolean[s.length()];
    // 记录正括号出现的下标
    Stack<Integer> stack = new Stack<>();
    for(int i=0;i<s.length();i++){ // 循环字符串
        char c = s.charAt(i); // 当前字符
        if('('==c){ // 如果是正括号
            stack.push(i); // 加入到Stack中
        }else if(')'==c){ // 如果是反括号
            if(stack.size()>0){ // 如果Stack中有正括号
                // pop出该正括号
                // 说明当前反括号与pop出的正括号是有效的
                stack.pop();
            }else{ // 如果Stack中没有正括号
                // 当前反括号是多余的，应被删除
                wrong[i]=true;
            }
        }
    }
    while(stack.size()>0){ // stack中剩余的正括号是多余的
        wrong[stack.pop()]=true;
    }
    StringBuilder sb = new StringBuilder(); // 返回结果
    for(int i=0;i<s.length();i++){
        if(!wrong[i]){ // 所有不需要被删除的字符可以组成返回结果
            sb.append(s.charAt(i));
        }
    }
    return sb.toString();
}

本题解法执行时间为29ms。

Runtime: 29 ms, faster than 49.12% of Java online submissions for Minimum Remove to Make Valid Parentheses.

Memory Usage: 38.4 MB, less than 100.00% of Java online submissions for Minimum Remove to Make Valid Parentheses.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1249-minimum-remove-to-make-valid-parentheses-解题思路分析/