Java实现 LeetCode 301 删除无效的括号

301. 删除无效的括号

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

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

示例 1:

输入: “()())()”

输出: ["()()()", “(())()”]

示例 2:

输入: “(a)())()”

输出: ["(a)()()", “(a())()”]

示例 3:

输入: “)(”

输出: [""]

class Solution {

    public List<String> removeInvalidParentheses(String s) {

        int left = 0, right = 0;

        char[] cs = s.toCharArray();

        for(char c : cs) {

            if(c == '(') {

                left++;

            }else if(c == ')') {

                if(left == 0) right++;

                else left--;

            }

        }

        List<String> res = new ArrayList<>();

        backtrace(cs, 0, new StringBuilder(s.length()-left-right), res, 0, 0, left, right);

        return res;

    }

    private void backtrace(char[] cs, int cur, StringBuilder sb, List<String> res,

                           int left, int right, int remL, int remR) {

        if(cur == cs.length) {

            if(remL == 0 && remR == 0) res.add(sb.toString());

            return;

        }

        if(right > left) return;

        final int len = sb.length();

        if(cs[cur] == '(') {

            // use

            sb.append('(');

            backtrace(cs, cur+1, sb, res, left+1, right, remL, remR);

            sb.setLength(len);

            if(remL > 0) { // not use

                while(cur < cs.length && cs[cur] == '(') { // find next

                    cur++;

                    remL--;

                }

                if(remL >= 0) backtrace(cs, cur, sb, res, left, right, remL, remR);

            }

        }else if(cs[cur] == ')') {

            // use

            sb.append(')');

            backtrace(cs, cur+1, sb, res, left, right+1, remL, remR);

            sb.setLength(len);

            if(remR > 0) { // not use

                while(cur < cs.length && cs[cur] == ')') { // find next

                    cur++;

                    remR--;

                }

                if(remR >= 0) backtrace(cs, cur, sb, res, left, right, remL, remR);

            }

        }else {

            sb.append(cs[cur]);

            backtrace(cs, cur+1, sb, res, left, right, remL, remR);

            sb.setLength(len);

        }

    }

}

巴特西

Java实现 LeetCode 301 删除无效的括号

301. 删除无效的括号

最新文章

热门文章