X

LEETCODE 301. Remove Invalid Parentheses 解题思路分析

删除无效的括号

删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。

说明: 输入可能包含了除 () 以外的字符。

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]

示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

示例 3:

输入: ")("
输出: [""]

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

解题思路分析:

  1. 首先确定字符串中不合理的左括号个数invalidLeft,以及不合理的右括号个数invalidRight。这个方法并不难。我们循环字符串,当遇到左括号时,invalidLeft加一。遇到右括号时,如果invalidLeft大于0,说明当前右括号可以和已有左括号配对,因此消耗一个左括号,即invalidLeft减一。反之如果此时invalidLeft等于0,说明当前出现的右括号之前没有能够配对的左括号,那么,invalidRight加一。重复在此过程,直到循环完所有字符为止。
  2. 以字符串首字符为起点进行dfs遍历操作,dfs方法中,需要如下参数:当前字符串,当前index,invalidRight和invalidLeft。显然,当invalidRight与invalidLeft同时为0时,当前字符串很有可能是一个有效结果,不过我们并不能确定,因此这里需要再次检查一下当前字符串是否合法,检查方法与第一步相同。如果当前字符串合理,将其加入返回结果。
  3. 接下来是invalidRight或者invalidLeft大于0的情况,我们最终的目的是消除掉所有的不合理字符,因此,我们从当前index向后遍历,如果当前字符是左括号”(“并且invalidLeft大于0,那么当前字符可以被删除,删除后,invalidLeft个数减一,index为当前下标,dfs至下层递归(继续从当前下标之后删除不合理字符)。同理,如果如果当前字符是右括号”)”并且invalidRight大于0,那么当前字符可以被删除,删除后,invalidRight个数减一,index为当前下标,dfs至下层递归。
  4. 最后考虑一下去重问题。最简单的方式是使用一个HashSet,然而这样做效率并不高。其实在第3步,我们有去重的方法。循环中,如果当前字符与前一字符相同的话,那么当前字符无论如何操作,实际上与前一字符的dfs逻辑没有任何区别,因此,当遇到连续的重复字符时,直接跳过即可。

总结:本题的核心思想是dfs深度优先搜索,我们可以将字符串中每个字符都看作是节点,每个节点的下一个节点集合是剩下的所有不合理节点。即当invalidLeft大于0时,当前下标之后的所有左括号都是不合理节点,同理,当invalidRight大于0时,当前下标之后的所有右括号也都是不合理节点。路径上选择的不同,也导致了多种返回结果的出现。

实现代码:

List<String> res=new ArrayList<>(); // 返回结果
public List<String> removeInvalidParentheses(String s) {
    int invalidLeft=0; // 不合理左括号个数
    int invalidRight=0; // 不合理右括号个数
    char[] arr=s.toCharArray();
    for(char c:arr){
        if(c=='(') invalidLeft++;
        if(c==')'){
            if(invalidLeft>0)invalidLeft--;
            else invalidRight++;
        }
    } // TODO 这部分代码可以与isValid方法合并

    dfs(s,invalidLeft,invalidRight,0); // dfs每一种删除方式
    return res;
}

void dfs(String s, int invalidLeft, int invalidRight, int index){
    if(invalidLeft==0&&invalidRight==0){ // 如果不合理括号已删除完
        if(isValid(s)) { // 查看当前字符串是否合理
            res.add(s); // 如果合理,加入返回结果
        }
        return;
    }
    if(index==s.length()){ // 如果下标越界,返回
        return;
    }

    for(int i=index;i<s.length();i++){ // 从当前下标向后循环
        char c = s.charAt(i); // 当前字符
        // 排重,如果当前字符与前一字符相同,跳过
        if(i>index&&c==s.charAt(i-1)) continue;
        // 如果当前字符是左括号,并且invalidLeft大于0
        if(c=='('&&invalidLeft>0){
            StringBuilder sb=new StringBuilder(s);
            sb.deleteCharAt(i); // 删除当前字符
            dfs(sb.toString(),invalidLeft-1,invalidRight,i); // dfs至下一节点
        }
        // 如果当前字符是右括号,并且invalidRight大于0
        if(c==')'&&invalidRight>0){
            StringBuilder sb=new StringBuilder(s);
            sb.deleteCharAt(i); // 删除当前字符
            dfs(sb.toString(),invalidLeft,invalidRight-1,i); // dfs至下一节点
        }
    }
}
// 判断字符串s是否合理
boolean isValid(String s){
    int invalidLeft=0;
    int invalidRight=0;
    char[] arr=s.toCharArray();
    for(char c:arr){
        if(c=='(') invalidLeft++;
        if(c==')'){
            if(invalidLeft>0)invalidLeft--;
            else invalidRight++;
        }
    }
    return invalidLeft==0&&invalidRight==0;
}

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

Runtime: 3 ms, faster than 77.81% of Java online submissions for Remove Invalid Parentheses.

Memory Usage: 39.6 MB, less than 71.60% of Java online submissions for Remove Invalid Parentheses.

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