DFS and BFS java solutions, add one more Optimized fast DFS solution


  • 5
    I
    // Optimized DFS Solution
    public class Solution {
        public List<String> removeInvalidParentheses(String s) {
            if (s.length() == 0) return new ArrayList<String>(Arrays.asList(""));
            Map<Integer, List<String>> dics = new HashMap<Integer, List<String>>();
            Set<String> visited = new HashSet<String>();
            int[] min = new int[]{Integer.MAX_VALUE};
            char[] str = s.toCharArray();
            helper(dics, str, 0, "", 0, 0, min, 0, visited);
            return dics.get(min[0]);
        }
        private void helper(Map<Integer, List<String>> dics, char[] str, int start, String cur, 
                            int left, int right, int[] min, int delete, Set<String> visited) {
            // Base Cases
            if (visited.contains(cur + delete)) return;
            visited.add(cur + delete);
            if (start == str.length) {
                if (left != right) return;
                if (!dics.containsKey(delete)) dics.put(delete, new ArrayList<String>());
                dics.get(delete).add(cur);
                min[0] = Math.min(min[0], delete);
                return;
            }
            if (left < right) return;
            if (str[start] == '(') {
                helper(dics, str, start + 1, cur + "(", left + 1, right, min, delete, visited);
                helper(dics, str, start + 1, cur, left, right, min, delete + 1, visited);
            } else if (str[start] == ')') {
                helper(dics, str, start + 1, cur + ")", left, right + 1, min, delete, visited);
                helper(dics, str, start + 1, cur, left, right, min, delete + 1, visited);
            } else {
                helper(dics, str, start + 1, cur + str[start], left, right, min, delete, visited);
            }
        }
    }
    
    // DFS 
    public class Solution {
        public List<String> removeInvalidParentheses(String s) {
            if (s.length() == 0) return new ArrayList<String>(Arrays.asList(""));
            Map<Integer, Set<String>> dics = new HashMap<Integer, Set<String>>();
            int[] min = new int[]{Integer.MAX_VALUE};
            char[] str = s.toCharArray();
            helper(dics, str, 0, "", 0, 0, min, 0);
            return new ArrayList<String>(dics.get(min[0]));
        }
        private void helper(Map<Integer, Set<String>> dics, char[] str, int start, String cur, 
                            int left, int right, int[] min, int delete) {
            // Base Cases
            if (start == str.length) {
                if (left != right) return;
                if (!dics.containsKey(delete)) dics.put(delete, new HashSet<String>());
                dics.get(delete).add(cur);
                min[0] = Math.min(min[0], delete);
                return;
            }
            if (left < right) return;
            if (str[start] == '(') {
                helper(dics, str, start + 1, cur + "(", left + 1, right, min, delete);
                helper(dics, str, start + 1, cur, left, right, min, delete + 1);
            } else if (str[start] == ')') {
                helper(dics, str, start + 1, cur + ")", left, right + 1, min, delete);
                helper(dics, str, start + 1, cur, left, right, min, delete + 1);
            } else {
                helper(dics, str, start + 1, cur + str[start], left, right, min, delete);
            }
        }
    }
    
    // BFS
    //idea from @jeantimex, modified and rewrite
    public class Solution {
        public List<String> removeInvalidParentheses(String s) {
            List<String> res = new ArrayList<String>();
            if (s == null) return res;
            Queue<String> queue = new LinkedList<String>();
            Set<String> visited = new HashSet<String>();
            queue.add(s);
            boolean reached = false;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String cur = queue.remove();
                    // Valid
                    if (isValid(cur)) {
                        reached = true;
                        res.add(cur);
                    }
                    // Not Valid Then Delete 
                    if (!reached) {
                        for (int j = 0; j < cur.length(); j++) {
                            if (cur.charAt(j) != '(' && cur.charAt(j) != ')') continue;
                            String newStr = cur.substring(0, j) + cur.substring(j + 1);
                            if (!visited.contains(newStr)) {
                                queue.add(newStr);
                                visited.add(newStr);
                            }
                        }
                    }
                }
                if (reached) break;
            }
            return res;
        }
        private boolean isValid(String str) {
            char[] s = str.toCharArray();
            int left = 0;
            for (int i = 0; i < s.length; i++) {
                if (s[i] == '(') left++;
                else if (s[i] == ')') {
                    if (left == 0) return false;
                    left--;
                }
            }
            return left == 0;
        }
    }

  • -1
    Y
      int possible_delete(string& s) {
        int l = 0, r = 0;
        for(const auto& ele : s) {
          if(ele == '(') {
              l++;
          }else if(ele == ')'){
              if(l == 0) {
                  r++;
              }else {
                  l--;
              }
          }
        }
        return l + r;
      }
    

    Use a helper function like this to limit the maximum num of delete can significantly improve the running time.


  • 0
    A

    For the BFS solution, shouldn't we check reached flag outside the for loop? We might run into this case: at some point we have a new level in the queue: A,B,C,D,E. We first check string A and B, neither of them are valid, so we enqueue all possible substrings by removing one parentheses from A and B; then we check string C and found C is valid, so we set the reached flag to true. Then we checked D and E. After that, we finished the for-loop for this level and we shouldn't check the queue again since we already got valid string from this level. But from your code, we will continue to check the queue since the queue is not empty. It has strings we got from A and B. You solution indeed pass all test cases, but I'm trying to think about an example case of the scenario I mentioned above..


  • 0
    I

    You are right. Updated code.


  • 0
    S

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

    The question says the possible valid answers are : "()()()", "(())()" , I am wondering why not "(()())" is a valid possibility.


  • 0
    I

    How can you generate "(()())" only by deleting one character from original string "()())()" ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.