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 ).

Examples:

"()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""]

链接： http://leetcode.com/problems/remove-invalid-parentheses/

题解：

给定String，去除invalid括号，输出所有结果集。一开始想的是DFS + Backtracking，没有坚持下去。后来在Discuss里发现了jeantimex大神的BFS方法非常好，于是搬过来借鉴。方法是我们每次去掉一个"("或者")"，然后把新的string加入到Queue里，继续进行计算。要注意的是需要设置一个boolean foundResult，假如在这一层找到结果的话，我们就不再继续进行下面的for循环了。这里应该还可以继续剪枝一下，比如记录当前这个结果的长度len，当queue里剩下的string长度比这个len小的话，我们不进行验证isValid这一步。

Time Complexity - O(n * 2ⁿ)， Space Complexity - O(2ⁿ)

public class Solution {public List<String> removeInvalidParentheses(String s) {List<String> res = new ArrayList<>();if(s == null) {return res;}Queue<String> queue = new LinkedList<>();Set<String> visited = new HashSet<>();queue.offer(s);boolean foundResult = false;while(!queue.isEmpty()) {s = queue.poll();if(isValid(s)) {res.add(s);foundResult = true;}if(foundResult) {continue;}for(int i = 0; i < s.length(); i++) {char c = s.charAt(i);if(c == '(' || c == ')') {String t = s.substring(0, i) + s.substring(i + 1);if(!visited.contains(t)) {queue.offer(t);visited.add(t);}}}}return res;}private boolean isValid(String s) {int leftCount = 0;for(int i = 0; i < s.length(); i++) {char c = s.charAt(i);if(c == '(') {leftCount++;} else if (c == ')') {leftCount--;}if(leftCount < 0) {return false;}}return leftCount == 0;} }

 

Reference:

https://leetcode.com/discuss/67842/share-my-java-bfs-solution

https://leetcode.com/discuss/67853/my-c-dfs-solution-16ms

https://leetcode.com/discuss/67919/java-optimized-dfs-solution-3-ms

https://leetcode.com/discuss/67861/short-python-bfs

https://leetcode.com/discuss/72208/easiest-9ms-java-solution

https://leetcode.com/discuss/67861/short-python-bfs

https://leetcode.com/discuss/72208/easiest-9ms-java-solution

https://leetcode.com/discuss/67908/java-bfs-solution-16ms-avoid-generating-duplicate-strings

https://leetcode.com/discuss/67821/and-bfs-java-solutions-add-more-optimized-fast-dfs-solution

https://leetcode.com/discuss/68038/clean-java-solution-bfs-optimization-40ms

https://leetcode.com/discuss/68010/fast-optimized-dfs-java-solution

 

总结

以上是生活随笔为你收集整理的301.Remove Invalid Parentheses的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。