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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。