21ms Java solution, precomputed max opening parens, loop to avoid duplicates, detailed explanation


  • 1
    Y
    public class Solution {
        public List<String> removeInvalidParentheses(String s) {
            // steps:
            // 1. compute the maximum number of opening parentheses that the longest valid sequence can take, as quotaOpen and quotaClose
            // 2. DFS for each pos, using a loop to avoid making duplicate binary decisions at continuous opening or closing parentheses
            List<String> result = new ArrayList<String>();
            int quotaOpen = maxOpenParen(s);
            int quotaClose = quotaOpen;
            removeInvalidParenthesesHelper(s.toCharArray(), 0, quotaOpen, quotaClose, new StringBuilder(), result);   
            return result;
        }
        
        private void removeInvalidParenthesesHelper(char[] array, int currInd, int quotaOpen, int quotaClose, StringBuilder sb, List<String> result) {
        	if (quotaOpen < 0 || quotaClose < 0 || quotaOpen > quotaClose) {
        		return;
        	}
        	if (currInd == array.length) {
                if (quotaOpen == 0 && quotaClose == 0) {
                    result.add(sb.toString());
                }
                return;
            }
            char currChar = array[currInd];
            // directly copy char that is not ( or )
            if (currChar != '(' && currChar != ')') {
                sb.append(currChar);
                removeInvalidParenthesesHelper(array, currInd + 1, quotaOpen, quotaClose, sb, result);
                sb.deleteCharAt(sb.length()-1);            
            } else if (currChar == '(') {
            	int end = currInd;
            	while (end < array.length && array[end] == '(') {
            		end++;
            	}
            	// loop to avoid making duplicate binary decisions at continuous parentheses
            	// directly taking 0 to (end-currInd) parentheses
            	for (int i = currInd; i <= end; i++) {
            		sb.append(array, currInd, i - currInd);
            		removeInvalidParenthesesHelper(array, end, quotaOpen - (i - currInd), quotaClose, sb, result);
            		sb.delete(sb.length() - (i - currInd), sb.length());
            	}	
            } else if (currChar == ')') { // similar to opening parentheses
            	int end = currInd;
            	while (end < array.length && array[end] == ')') {
            		end++;
            	}
            	for (int i= currInd; i <= end; i++) {	
            		sb.append(array, currInd, i - currInd);
            		removeInvalidParenthesesHelper(array, end, quotaOpen, quotaClose - (i - currInd), sb, result);
            		sb.delete(sb.length() - (i - currInd), sb.length());
            	}
            }
        }
        
        private int maxOpenParen(String s) {
            char[] array = s.toCharArray();
            int maxOpen = 0;
            int stack = 0; // for opening parentheses seen thus far
            for (int i = 0; i < array.length; i++) {
            	if (array[i] == '(') {
            		stack++;
            	} else if (array[i] == ')' && stack > 0) {
            		stack--;
            		maxOpen++;
            	}
            }
            return maxOpen;
        }
    }

Log in to reply
 

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