Java optimized DFS solution 3 ms


  • 20
    W

    DFS solution with optimizations:

    1. Before starting DFS, calculate the total numbers of opening and closing parentheses that need to be removed in the final solution, then these two numbers could be used to speed up the DFS process.
    2. Use while loop to avoid duplicate result in DFS, instead of using HashSet.
    3. Use count variable to validate the parentheses dynamically.

     public class Solution {
        public List<String> removeInvalidParentheses(String s) {
            int count = 0, openN = 0, closeN = 0;
    
            // calculate the total numbers of opening and closing parentheses
            // that need to be removed in the final solution
            for (char c : s.toCharArray()) {
                if (c == '(') {
                    count++;
                } else if (c == ')') {
                    if (count == 0) closeN++;
                    else count--;
                }
            }
            openN = count;
            count = 0;
    
            if (openN == 0 && closeN == 0) return Arrays.asList(s);
    
            List<String> result = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
    
            dfs(s.toCharArray(), 0, count, openN, closeN, result, sb);
    
            return result;
        }
    
        private void dfs(char[] s, int p, int count, int openN, int closeN, List<String> result, StringBuilder sb) {
            if (count < 0) return; // the parentheses is invalid
    
            if (p == s.length) {
                if (openN == 0 && closeN == 0) { // the minimum number of invalid parentheses have been removed
                    result.add(sb.toString());
                }
                return;
            }
    
            if (s[p] != '(' && s[p] != ')') {
                sb.append(s[p]);
                dfs(s, p + 1, count, openN, closeN, result, sb);
                sb.deleteCharAt(sb.length() - 1);
            } else if (s[p] == '(') {
                int i = 1;
                while (p + i < s.length && s[p + i] == '(') i++; // use while loop to avoid duplicate result in DFS, instead of using HashSet
                sb.append(s, p, i);
                dfs(s, p + i, count + i, openN, closeN, result, sb);
                sb.delete(sb.length() - i, sb.length());
    
                if (openN > 0) {
                    // remove the current opening parenthesis
                    dfs(s, p + 1, count, openN - 1, closeN, result, sb);
                }
            } else {
                int i = 1;
                while (p + i < s.length && s[p + i] == ')') i++; // use while loop to avoid duplicate result in DFS, instead of using HashSet
                sb.append(s, p, i);
                dfs(s, p + i, count - i, openN, closeN, result, sb);
                sb.delete(sb.length() - i, sb.length());
    
                if (closeN > 0) {
                    // remove the current closing parenthesis
                    dfs(s, p + 1, count, openN, closeN - 1, result, sb);
                }
            }
        }
    }

  • 0
    Y

    Hi, your code looks very efficient. yet what is the exact meaning of openN and count?

    Initially they are

        openN = count;
        count = 0;
    

    what does it mean?

    Later, you have something like:

            dfs(s, p + i, count + i, openN, closeN, result, sb);
            if (openN > 0) {
              dfs(s, p + 1, count, openN - 1, closeN, result, sb);
    

    why do you update them differently?

    Thanks!


  • 0
    W

    openN and closeN means the total numbers of opening and closing parentheses that need to be removed in the final solution (removed the minimum number of invalid parentheses).

    dfs(s, p + i, count + i, openN, closeN, result, sb) means not to remove the current parenthesis.

    dfs(s, p + 1, count, openN - 1, closeN, result, sb) means to remove the current parenthesis. We won't need to do the dfs if openN has been decreased to zero - if the openN is zero, that means there are already enough open parentheses has been removed, and continually removing open parenthesis won't be a possible solution.


  • 0
    N

    What would be the time and space complexity for this solution ?


Log in to reply
 

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