Share my JAVA code with explanation


  • 0
    S

    idea:
    hashset to remember which string has been visited before.
    add s to queue
    if valid, add s to the result; note: if the first s in the queue is valid, any rest actions of removing one
    '(' or ')' would NOT generate valid parentheses, so it is redundant, so better return first.
    Then try to remove any'(' or ')' from s, and build a new string,
    for these newly built strings, just leave them be dealt with later by only adding to the queue.

    public class RemoveInvalidParentheses {
        public List<String> removeInvalidParentheses(String s) {
            List<String> result = new ArrayList<String>();
            if (s.length() == 0 || s == null) {
                result.add(s);
                return result;
            }
            HashSet<String> hs = new HashSet<String>();
            Queue<String> queue = new LinkedList<String>();
            queue.offer(s);
            hs.add(s);
            
            boolean found = false;
    
            while (!queue.isEmpty()) {
                s = queue.poll();
                if (isValidParentheses(s)) {
                    found = true;
                    result.add(s);
                    // some optimization for edge case
                    // if the string s already a valid parenthesee, no need to remove any '('' or ')' later
                    // save some time
                    if (queue.size() == 0) {
                        return result;
                    }
                }
                if (found) {
                    continue;
                }
                for (int i = 0; i < s.length(); i++) {
                    char c = s.charAt(i);
                    if (c != '(' && c != ')') {
                        continue;
                    }
                    String temp = s.substring(0, i) + s.substring(i+1);
                    // add() returns false if the string alreay in the hashset
                    if (hs.add(temp)) {
                        queue.offer(temp);
                    }
                }
            }
            return result;
        }
        // helper to determine if a string is a valid parenthesis
        private boolean isValidParentheses(String s) {
            int cnt = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    cnt++;
                }
                if (s.charAt(i) == ')') {
                    if (cnt == 0) {
                        return false;
                    }
                    cnt--;
                }
            }
    
            return cnt == 0;
        }
    }```

Log in to reply
 

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