1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
|
import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Queue;
public class {
public static List<String> removeInvalidParentheses(String s) { HashSet<String> visited = new HashSet<>(); Queue<String> q = new LinkedList<>(); List<String> res = new LinkedList<>(); boolean found = false; q.offer(s);
while(!q.isEmpty()){ s = q.poll();
if (isValid(s)){ found = true; res.add(s); }
if (found) continue;
for (int i=0; i<s.length(); i++){ if (s.charAt(i) == '(' || s.charAt(i) == ')') { String t = s.substring(0, i) + s.substring(i+1); if (!visited.contains(t)){ q.offer(t); visited.add(t); } } } } return res;
} public static void main(String[] args) { String s = "(())())"; for (String ss: removeInvalidParentheses(s)){ System.out.println(ss); } } public static boolean isValid(String s){ int count = 0; for (int i=0; i<s.length(); i++) { if (s.charAt(i) == '(') count ++; if (s.charAt(i) == ')') { if (--count < 0) return false; } } return count == 0; } }
|
近期评论