Java solution using DFS with a little pre-optimization


  • 0
    B

    Here is my solution.
    For those string starting with ")", it can be removed because there is no way to form a valid parentheses without "(" ahead. Thus, shorten the string length that we need DFS.

    As well, for those characters ending with "(", there is no way to form a valid parentheses, so just delete them.

    After pre-handling the string, we process the string to choose any position character to delete (expect 'a'..'z'). The way I process String is s.substring(0, i) + s.substring(i + 1, s.length()).

    Down below is my code, and I think better solution is on the way. :)

    public class RemoveInvalidParentheses {
        private List<String> ans = new ArrayList<String>();
        private int min = Integer.MAX_VALUE;
    
        public List<String> removeInvalidParentheses(String s) {
            int i = 0;
            while (i < s.length() && s.charAt(i) == ')') s = s.substring(1);
            i = s.length();
            while (i > 0 && s.charAt(i - 1) == '(') {
                s = s.substring(0, i - 1);
                i = s.length();
            }
            for (i = 0; i < s.length(); i++)
                if (s.charAt(i) == '(') left++;
                else if (s.charAt(i) == ')') right++;
            helper(0, s, left, right, 0);
            return ans;
        }
    
        private boolean isValid(String s) {
            if (s == null || s.length() == 0) return true;
            Stack<Character> stack = new Stack<Character>();
            int i = 0;
            while (i < s.length()) {
                if (s.charAt(i) == '(') stack.push(s.charAt(i));
                else if (s.charAt(i) == ')') {
                    if (stack.isEmpty() || stack.peek() != '(') return false;
                    stack.pop();
                }
                i++;
            }
            return (stack.isEmpty());
        }
    
        private void helper(int times, String s, int l, int r, int idx) {
            if (times > min) return;
            if (isValid(s)) {
                if (times < min) {
                    min = times;
                    ans = new ArrayList<String>();
                    ans.add(new String(s));
                    return;
                } else {
                    if (!ans.contains(s))
                        ans.add(new String(s));
                    return;
                }
            }
            
            for (int i = idx; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    helper(times + 1, s.substring(0, i) + s.substring(i + 1, s.length()), l - 1, r, i);
                } else if (s.charAt(i) == ')') {
                    helper(times + 1, s.substring(0, i) + s.substring(i + 1, s.length()), l, r - 1, i);
                } 
            }
        }
    }

  • 0
    Y

    May I know the actual run time of this program?


  • 0
    H

    My given solution runs in 119 ms with Java.
    Initially, I added some large test cases to prevent intuitive backtracking solution to get AC.
    But later Admin @1337c0d3r told me it may also prevent slow languages to get AC even it is written in correct way, so those large test cases are removed.


Log in to reply
 

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