Concise Java DFS Solution with memorizing


  • 0
    D
    public List<String> removeInvalidParentheses(String s) {
      List<String> res = new ArrayList<>();
      if (s == null) return res;
      Set<String> visited = new HashSet<>();
      Set<String> set = new HashSet<>();
      // Find all of possible strings which are valid parentheses
      // Store all of them to set
      // To optimalize, use visited variable for memorizaiton 
      dfs(s, set, visited);
      // Finding the max length of string means removing the minimum number of invalid parentheses  
      int max = 0;
      for (String str : set) {
          max = Math.max(str.length(), max);
      }
      for (String str : set) {
          if (str.length() == max) res.add(str);
      }
      return res;
    }
    
    void dfs(String s, Set<String> set, Set<String> visited) {
        if (set.contains(s) || visited.contains(s)) return;
        if (isValid(s)) {
            set.add(s);
            return;
        }
        visited.add(s);
        for (int i = 0 ; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')' || c == '(') {
                String s1 = s.substring(0, i);
                String s2 = s.substring(i + 1);
                dfs(s1 + s2, set, visited);
            }
        }
    }
    
    boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')'){
                count--;
                if (count < 0) return false;
            }
        }
        return count == 0;
    }

Log in to reply
 

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