Simple JAVA BFS Solution


  • 0
    K

    public class Solution {

    public List<String> removeInvalidParentheses(String s) {
        if (s == null) {
            return null;
        }
        
        List<String> list = new ArrayList<>();
        Set<String> next = new HashSet<>();
        next.add(s);
        
        while (list.isEmpty()) {
            Set<String> newNext = new HashSet<>();
            for (String str: next) {
                add(str, list);
                for (int i = 0; i < str.length(); i++) {
                    newNext.add(new StringBuilder(str).deleteCharAt(i).toString());
                }
            }
            next = newNext;
        }
        return list;
    }
    
    private void add(String s, List<String> list) {
        if (valid(s)) {
            list.add(s);
            return;
        }
        String removed;
        for (int i = 0; i < s.length(); i++) {
            removed = new StringBuilder(s).deleteCharAt(i).toString();
            if (valid(removed)) {
                if (!list.contains(removed)) {
                    list.add(removed);
                }
            }
        }
    }
    
    private boolean valid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char ch: s.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    

    }


Log in to reply
 

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