[leetcode]Remove Invalid Parentheses

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

public class Solution { public List<String> removeInvalidParentheses(String s) { List<String> result = new ArrayList<String>(); HashSet<String> lookup = new HashSet<String>(); Queue<String> queue = new LinkedList<String>(); queue.add(s); queue.add(null); while (!queue.isEmpty()){ String current = queue.poll(); if (current == null){ if (result.size() != 0) break; queue.add(null); } if (current != null && !lookup.contains(current)){ lookup.add(current); if (isValid(current)) result.add(current); else{ for (int i = 0; i < current.length(); i++){ char temp = current.charAt(i); if (temp == '(' || temp == ')'){ queue.add(current.substring(0,i)+current.substring(i+1)); } } } } } return result; } private boolean isValid(String s){ int count = 0; for (int i = 0; i < s.length(); i++){ char current = s.charAt(i); if (current == '(') count++; else if (current == ')') count--; if (count < 0) return false; } return count == 0; } }