My easily understandable dfs solution


  • -1
    S

    the logic is using a counter c to indicate if the Parentheses is valid .

    if current char is ')' and c != 0 we need to find if the maximum Parentheses include the current char or not , the same logic could be also applied when current char is '('

    the key logic is including or not

    public List<String> removeInvalidParentheses(String s) {
    		  List<String> rst = new ArrayList<> ();
    		  if (s == null || s.length() == 0) {
    			  rst.add("") ;
    			  return rst ;
    		  }
    		  HashMap<Integer,Set<String>> map = new HashMap<> ();
    	      int min = findMin (0,0, s, 0, "", map);	      
    	      return new ArrayList<String> (map.get(min)) ;    
    	  }
    	
    	
    	public int findMin (int index, int c, String exp, int rm, String cur, HashMap<Integer, Set<String>> map){
    		if (index >= exp.length() && c == 0) {
    			Set<String> set = map.containsKey(rm) ? map.get(rm) : new HashSet<String> ();
    			set.add(cur) ;
    			map.put(rm, set) ;
    		   return rm ;
    		}		
    		if(index >= exp.length()) {
    			return Integer.MAX_VALUE ;
    		}
    		if (exp.charAt(index) == ')') {
    			if (c == 0) {
    				return findMin(index + 1, c, exp, rm + 1, cur, map);	
    			} else {
    				return Math.min(findMin(index + 1, c ,exp, rm + 1, cur, map), findMin(index + 1, c - 1 ,exp, rm, cur + ")", map)) ;
    			}			
    		} else if (exp.charAt(index) == '(') {
    			return Math.min(findMin(index + 1, c, exp, rm + 1, cur, map), findMin(index + 1, c + 1 , exp, rm, cur + "(", map));
    		} else {
    			return findMin (index + 1, c, exp, rm, cur + exp.charAt(index), map) ;
    		}
    	}

Log in to reply
 

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