301.删除无效的括号

题目描述

题解

回溯算法

对于一个字符串, 首先可以根据这个字符串中左右括号的数量确定出需要删除多少个左括号或者右括号. 要么删若干个左括号, 要么删若干个右括号, 不可能存在左右括号都删除的情况.

在这个基础上, 对整个字符串进行回溯. 例如一共要删除两个左括号, 那么遍历整个字符串时, 如果碰到了左括号, 把它删除试试, 然后判断.

public class lc301 {
    List<String> ans = new ArrayList<>();

    public List<String> removeInvalidParentheses(String s) {
        if (s.length() == 0) {
            return ans;
        }

        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            }
            if (s.charAt(i) == ')') {
                if (left > 0) {
                    left--;
                } else {
                    right++;
                }
            }
        }

        dfs(s, 0, left, right);
        return ans;
    }

    private void dfs(String s, int st, int left, int right) {
        if (left == 0 && right == 0) {
            if (check(s)) {
                ans.add(s);
            }
            return;
        }

        for (int i = st; i < s.length(); i++) {
            // 去重
            if (i > st && s.charAt(i) == s.charAt(i - 1)) {
                continue;
            }
            String subStr = s.substring(0, i) + s.substring(i + 1);
            if (left > 0 && s.charAt(i) == '(') {
                dfs(subStr, i, left - 1, right);
            } else if (right > 0 && s.charAt(i) == ')') {
                dfs(subStr, i, left, right - 1);
            }
        }
    }

    private boolean check(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            }
            if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }

    @Test
    public void test() {
        lc301 lc301 = new lc301();
        String test = "()())()";
        System.out.println(lc301.removeInvalidParentheses(test));
    }
}