Remove Invalid Parentheses

LeetCode Q 301 - Remove Invalid Parentheses

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: [""]

Solution : DFS

1. pre-process the String s, determine how many (s and )s we need to delete.
2. To avoid duplicates, use a set to store the result.
3. Backtrack finding the answer.
   • corner cases: if (rmL < 0 || rmR < 0 || open < 0) indicates an invalid string, we should return;
   • our goal(i.e. when to break the backtrack): if (pos == s.length()) we should also stop the backtrack, and check
     • if (rmL == 0 && rmR == 0 && open == 0), then update the result set;
     • else just ruturn;
   • explore
     • if current char is ‘(‘ or ‘)’ we can either choose to use it or not.
     • if current char is a letter we update current string.

Code:

Set<String> res; // avoid duplicates
public List<String> removeInvalidParentheses(String s) {
	res = new HashSet<>();
	int rmL = 0, rmR = 0;
	for (char ch: s.toCharArray()) {
		if (ch == '(') {
			rmL++;
		} else if (ch == ')') {
			if (rmL != 0) rmL--;
			else rmR++;
		}
	}

	dfs(s, 0, "", rmL, rmR, open);

	return new ArrayList(res);
}

private void dfs(String s, int pos, String curr, int rmL, int rmR, int open) {
	if (rmL < 0 || rmR < 0 || open < 0) return;

	if (pos == s.length()) {
		if (rmL == 0 && rmR == 0 && open == 0) res.add(curr);
		return;
	}

	char ch = s.charAt(pos);
	if (ch == '(') {
		dfs(s, pos + 1, curr + ch, rmL, rmR, open + 1); // use '('
		dfs(s, pos + 1, curr, rmL - 1, rmR, open); // not use '('
	} else if (ch == ')') {
		dfs(s, pos + 1, curr + ch, rmL, rmR, open - 1); // use ')'
		dfs(s, pos + 1, curr, rmL, rmR - 1, open); // not use ')'
	} else {
		dfs(s, pos + 1, curr + ch, rmL, rmR, open);
	}

	return;
}