Clean Java solution, BFS + optimization, 40ms


  • 4
    J

    Solution based earlier posts on this forum.

     public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
        	ans.add("");
        	return ans;
        }
        
        //Remove proceeding ")".
        int i = 0;
        while (i < s.length() && s.charAt(i) != '(') i++;
        s = s.substring(0, i).replace(")", "") + ((i == s.length())?"" : s.substring(i));
        
        //Remove trailing "("
        int j = s.length() - 1;
        while (j >= 0 && s.charAt(j) != ')') j--;
        s = s.substring(0, j+1) + ((j == s.length()-1)? "" : s.substring(j+1).replace("(", ""));
        
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(s);
        visited.add(s);
        boolean found = false;
        while (!q.isEmpty()) {
        	s = q.poll();
        	if (isValid(s)) {
        		ans.add(s);
        		found = true;
        	}
        	if (found) continue;
        	for (int k = 0; k < s.length(); k++) {
        		if (s.charAt(k) != '(' && s.charAt(k) != ')') 
        			continue;
        		//Avoid dup.
        		if (k > 0 && s.charAt(k) == s.charAt(k-1)) 
        			continue;
        		String t = s.substring(0,k) + s.substring(k+1);
        		if (!visited.contains(t)) {
        			q.offer(t);
        			visited.add(t);
        		}
        	}
        }
        return ans;
    }
    
    private 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;
    }

  • 0
    A

    Why do u make the removal of leading and trailing invalid braces complex, can't u just use:

            int k = 0;
            while(k < s.length() && s.charAt(k) == ')')
                k++;
            s = s.substring(k);
            k = s.length() - 1;
            while(k >= 0 && s.charAt(k) == '(')
                k--;
            s = s.substring(0,k+1);
    

    and then follow on with the same logic?


Log in to reply
 

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