LeetCode刷题之删除无效括号

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

题目描述

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例1 ：

输入：s = "()())()"
输出：["(())()","()()()"]
复制代码

示例2 ：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
复制代码

示例3 ：

输入：s = ")("
输出：[""]
复制代码

思路：DFS+剪枝

• 从左向右遍历字符串，只要出现右括号比左括号多的情况，可以删除前面任意一个右括号，进入下次递归。
• 如果一直不出现右括号比左括号多的情况，说明右括号已经删除完毕，这时可能有多余的左括号
• 从右向左遍历字符串，删除可能的多余左括号，与删除右括号逻辑一致

class Solution {
    public List<String> removeInvalidParentheses(String s) {
                List<String> result = new ArrayList<>();
        if (s.equals("()") || s.equals("")) {
            result.add(s);
            return result;
        }

        Deque<String> queue = new ArrayDeque<>();
        queue.offer(s);
        HashSet<String> set = new HashSet<>();  //用于存储裁剪后的元素，防止重复元素加入队列
        boolean isFound = false;    //判断是否找到了有效字符串

        while (!queue.isEmpty()) {  //队列不为空
            for(String cur:queue){
                if (isValid(cur)) {
                    result.add(cur);
                    isFound = true;
                }
            }
            if (isFound) {  //找到后不再进行裁剪
                break;
            }
            //裁剪过
            Deque<String> queue2 = new ArrayDeque<>();
            for( String curr:queue) {
                for (int i = 0; i < curr.length(); i++) {
                    if (curr.charAt(i) == '(' || curr.charAt(i) == ')') {   //只对'('或')'进行裁剪
                        String str;
                        if (i == curr.length() - 1) {
                            str = curr.substring(0, curr.length() - 1);
                        } else {
                            str = curr.substring(0, i) + curr.substring(i + 1);
                        }
                        if (set.add(str)) { //如果集合中还未有该字符串
                            queue2.offer(str);
                        }
                    }
                }
            }
            queue = queue2;
        }

        if (result.isEmpty()) {
            result.add("");
        }
        return result;
    }
    private static boolean isValid(String s) {
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            int curr = s.charAt(i);
            if (curr == '(') {
                left++;
            } else if (curr == ')') {
                if (left != 0) {
                    left--;
                } else {
                    return false;
                }
            }
        }
        return left == 0;
    }
}
复制代码