301.删除无效括号

给定一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。
示例1：

输入：s = “()())()”
输出：["(())()","()()()"]

示例2：

输入：s = “(a)())()”
输出：["(a())()","(a)()()"]

示例3：

输入：s = “)(”
输出：[""]

思路：对于每个左括号，都有一个对应的右括号。我们可以使用两个计数器来跟踪错位的左括号和右括号，在一次迭代中，我们可以找到这两个值。
例如：

i = 0, left = 1, right = 0
i = 1, left = 0, right = 0
i = 2, left = 0, right = 1
i = 3, left = 0, right = 2
i = 4, left = 1, right = 2
i = 5, left = 2, right = 2
i = 6, left = 3, right = 2
i = 7, left = 2, right = 2

根据最后结果显示，有两个错放的左括号和两个错放的右括号。
因此，其基本思路可以概括为：
1、计算需要去除的括号数；
2、回溯，将leftDelete和rightDelete降为0；
3、判断s是否有效。
判断方法：把括号压栈，如果是有效括号“（）”，就统一弹栈，如果一直有效，栈为空，则s有效，如果是“）（”，栈不为空，就是s无效。
代码：

class Solution {
	StringBuilder sb = new StringBuilder();
	Set<String> res = new HashSet<>();

	public List<String> removeInvalidParentheses(String s) {
		int leftDelete = 0;
		int rightDelete = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				leftDelete++;
			} else if (s.charAt(i) == ')') {
				rightDelete = leftDelete == 0 ? rightDelete + 1 : rightDelete;
				leftDelete = leftDelete > 0 ? leftDelete - 1 : leftDelete;
			}
		}
		helper(s, 0, 0, 0, leftDelete, rightDelete);
		return new ArrayList<>(res);
	}

	public void helper(String s, int index, int numOfLeft, int numOfRight, int leftDelete, int rightDelete) {
		// 已经遍历到字符串尾部
		if (index == s.length()) {
			if (leftDelete == 0 && rightDelete == 0)
				res.add(sb.toString());

		} else if (numOfRight > numOfLeft) {
			return;
		} else {
			char c = s.charAt(index);
			// 优先不添加括号
			if ((c == '(' && leftDelete > 0) || (c == ')' && rightDelete > 0)) {
				helper(s, index + 1, numOfLeft, numOfRight, leftDelete - (c == '(' ? 1 : 0),
						rightDelete - (c == ')' ? 1 : 0));
			}
			sb.append(c);
			if (c != '(' && c != ')') {
				helper(s, index + 1, numOfLeft, numOfRight, leftDelete, rightDelete);
			} else if (c == '(') {
				helper(s, index + 1, numOfLeft + 1, numOfRight, leftDelete, rightDelete);
			} else {
				helper(s, index + 1, numOfLeft, numOfRight + 1, leftDelete, rightDelete);
			}
			sb.deleteCharAt(sb.length() - 1);
		}
	}
}

执行结果：

总结： LeetCode第一天打卡就遇到了困难的题，在看到题后就有了想放弃的想法，但是还是坚持一步步的去理解题目，理清思路，虽然代码是在看视频查资料后完成的，但还是收获了很多，对自己的代码能力的提升有很大的帮助。