LeetCode刷题：301. Remove Invalid Parentheses
原题链接：https://leetcode.com/problems/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: [""]
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
DFS算法设计
/*DFS*/ public List<String> removeInvalidParentheses(String s) { List<String> ans = new ArrayList<>(); if (s == null) return ans; int removeLeft = 0, removeRight = 0; for (char ch : s.toCharArray()) { if (ch == '(') removeLeft++; if (ch == ')') { if (removeLeft > 0) removeLeft--; else removeRight++; } } DFS(s, 0, removeLeft, removeRight, ans); return ans; //O(string length) + O() } private void DFS(String s, int lastRemoveIndex, int removeLeft, int removeRight, List<String> ans) { if (removeLeft == 0 && removeRight == 0) { //O(N) if (isValid(s)) ans.add(s); return; } int idx = lastRemoveIndex; if (removeRight > 0) { while (idx < s.length()) { if (s.charAt(idx) == ')') { DFS(s.substring(0, idx) + s.substring(idx + 1, s.length()), idx, removeLeft, removeRight - 1, ans); while (idx < s.length() && s.charAt(idx) == ')') idx++; } else { idx++; } } return; } if (removeLeft > 0) { while (idx < s.length()) { if (s.charAt(idx) == '(') { DFS(s.substring(0, idx) + s.substring(idx + 1, s.length()), idx, removeLeft - 1, removeRight, ans); while (idx < s.length() && s.charAt(idx) == '(') idx++; } else { idx++; } } } } private boolean isValid(String s) { if (s == null) return false; int cnt = 0; for (char ch : s.toCharArray()) { if (ch == '(') cnt++; if (ch == ')') cnt--; if (cnt < 0) return false; } return cnt == 0; }
BFS算法设计
/* * BFS * */ public List<String> removeInvalidParentheses(String s) { List<String> res = new ArrayList<>(); // sanity check if (s == null) return res; Set<String> visited = new HashSet<>(); Queue<String> queue = new LinkedList<>(); // initialize queue.add(s); visited.add(s); boolean found = false; while (!queue.isEmpty()) { s = queue.poll(); if (isValid(s)) { // found an answer, add to the result res.add(s); found = true; } if (found) continue; // generate all possible states for (int i = 0; i < s.length(); i++) { // we only try to remove left or right paren if (s.charAt(i) != '(' && s.charAt(i) != ')') continue; String t = s.substring(0, i) + s.substring(i + 1); if (!visited.contains(t)) { // for each state, if it's not visited, add it to the queue queue.add(t); visited.add(t); } } } return res; } // helper function checks if string s contains valid parantheses boolean isValid(String s) { int count = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') count++; if (c == ')' && count-- == 0) return false; } return count == 0; }
