301. Remove Invalid Parentheses

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Example 2:

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]

Example 3:

Input: s = ")("
Output: [""]

Constraints:

• 1 <= s.length <= 25
• s consists of lowercase English letters and parentheses '(' and ')'.
• There will be at most 20 parentheses in s.

Code

class Solution {
    List<String> res;

    public List<String> removeInvalidParentheses(String s) {
        res = new ArrayList<>();
        removeHelper(s, 0, 0, '(', ')');
        return res;
    }

    public void removeHelper(String s, int iStart, int jStart, char left, char right) {
        int leftCount = 0, rightCount = 0;

        for (int i = iStart; i < s.length(); i++) {
            if (s.charAt(i) == left)
                leftCount++;
            if (s.charAt(i) == right)
                rightCount++;

            // extra right, need to remove
            if (rightCount > leftCount) {
                // 在i之前找到 ) 并且remove
                for (int j = jStart; j <= i; j++) {
                    // skip duplicates 只remove每组 ) 中的第一个
                    if (s.charAt(j) == right && (j == jStart || s.charAt(j - 1) != right)) {
                        String curr = s.substring(0, j) + s.substring(j + 1, s.length());
                        removeHelper(curr, i, j, left, right);
                    }
                }

                return;
            }
        }

        // valid right parenthesis detected
        // now check opposite direction
        String reversed = new StringBuilder(s).reverse().toString();
        if (left == '(') {
            removeHelper(reversed, 0, 0, ')', '(');
        } else {
            res.add(reversed);
        }
    }
}