[LeetCode] Remove Invalid Parentheses

本文主要是介绍[LeetCode] 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 ).

Examples:

“()())()” -> [“()()()”, “(())()”]
“(a)())()” -> [“(a)()()”, “(a())()”]
“)(” -> [“”]

解题思路

括号总是成对出现的，因此我们只需要记录尚未匹配的（。
每次循环时有如下三种情况：

(, 保留或者不保留。
), 如果我们有未匹配的（，则有两种选择；否则，只能不保留。
保留其他字符。

因为我们要移除数量最少的括号，我们应该得到最大的匹配（）数量，注意下面两行的顺序。

dfs(str.substring(1), subRes + '(', countLeft + 1, maxLeft + 1);
dfs(str.substring(1), subRes, countLeft, maxLeft);

它可以保证最长的结果出现在比它较短的结果前面。

实现代码

Java：

// Runtime: 216 ms
public class Solution {private List<String> res = new ArrayList<String>();private int max = 0;public List<String> removeInvalidParentheses(String s) {dfs(s, "", 0, 0);if (res.size() == 0) {res.add("");}return res;}private void dfs(String str, String subRes, int countLeft, int maxLeft) {if (str.length() == 0) {if (countLeft == 0 && subRes.length() != 0) {if (maxLeft > max) {max = maxLeft;}if (max == maxLeft && !res.contains(subRes)) {res.add(subRes.toString());}}return;}if (str.charAt(0) == '(') {dfs(str.substring(1), subRes.concat("("), countLeft + 1, maxLeft + 1);dfs(str.substring(1), subRes, countLeft, maxLeft);} else if (str.charAt(0) == ')') {if (countLeft > 0) {dfs(str.substring(1), subRes.concat(")"), countLeft - 1, maxLeft);}dfs(str.substring(1), subRes, countLeft, maxLeft);} else {dfs(str.substring(1), subRes.concat(String.valueOf(str.charAt(0))), countLeft, maxLeft);}}
}