301. Remove Invalid Parentheses

301. Remove Invalid Parentheses (Hard)

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

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

Example 2:

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

Example 3:

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

Related Topics:
Depth-first Search, Breadth-first Search

Similar Questions:

• Valid Parentheses (Easy)

Solution 1. Backtracking

// OJ: https://leetcode.com/problems/remove-invalid-parentheses/
// Author: github.com/lzl124631x
// Time: O(2^N)
// Space: O(N)
class Solution {
    unordered_set<string> ans;
    string tmp;
    int totalLeft = 0, totalRight = 0;
    void dfs(string &s, int i, int invalidLeft, int invalidRight, int visitedLeft, int visitedRight, int curLeft, int curRight) {
        if (curRight > curLeft) return;
        if (i == s.size()) {
            if (curLeft != curRight) return;
            ans.insert(tmp);
            return;
        }
        if ((s[i] != '(' && s[i] != ')')
            || (s[i] == '(' && invalidLeft == 0)
            || (s[i] == ')' && invalidRight == 0)) {
            tmp.push_back(s[i]);
            dfs(s, i + 1, invalidLeft, invalidRight, visitedLeft + (s[i] == '('), visitedRight + (s[i] == ')'), curLeft + (s[i] == '('), curRight + (s[i] == ')') );
            tmp.pop_back();
            return;
        }
        if (s[i] == '(') {
            if (totalLeft - visitedLeft >= invalidLeft) dfs(s, i + 1, invalidLeft - 1, invalidRight, visitedLeft + 1, visitedRight, curLeft, curRight);
            tmp.push_back(s[i]);
            dfs(s, i + 1, invalidLeft, invalidRight, visitedLeft + 1, visitedRight, curLeft + 1, curRight);
            tmp.pop_back();
        } else {
            if (totalRight - visitedRight >= invalidRight) dfs(s, i + 1, invalidLeft, invalidRight - 1, visitedLeft, visitedRight + 1, curLeft, curRight);
            tmp.push_back(s[i]);
            dfs(s, i + 1, invalidLeft, invalidRight, visitedLeft, visitedRight + 1, curLeft, curRight + 1);
            tmp.pop_back();
        }
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        int left = 0, right = 0;
        for (char c : s) {
            if (c != '(' && c != ')') continue;
            totalLeft += c == '(';
            totalRight += c == ')';
            if (c == '(') ++left;
            else if (!left) ++right;
            else --left;
        }
        if (s.size() == left + right) return {""};
        dfs(s, 0, left, right, 0, 0, 0, 0);
        return vector<string>(begin(ans), end(ans));
    }
};