Java DFS, Straight Forward with Detailed Explanation


  • 1
    Y

    The idea of this DFS is pretty simple. Just traverse the array.
    I used a char array and boolean array to mark which char to remove. Doing this is to avoid slow String processing of Java. Only in the final step did I construct the result array.

    While traversing the array, you will encounter three options.
    Left Parentheses
    Right Parentheses
    Other chars.

    For other chars, no need to process it.

    For Left Parentheses, push it into the stack (Actually list, because I found that stack cannot fulfill my request anymore.)
    The stack contains the index of the left parentheses.

    For Right Parentheses, first check if the stack is empty.

    If it is empty, it is an invalid right parentheses.
    We need to remove any right parentheses before, including itself.
    However, if we encounter consecutive right ones, only one needs to be removed as they will produce the same result.

    If the stack is not empty, we still cannot pop one from stack easily. We can have multiple matching strategy on that. We can match any of the Left Parentheses to this right parentheses. We will find that if there is any left parentheses left when I reached an end, we could ignore some of the left ones.

    When it reached an end, if the stack has anything left, just remove these chars.
    The program are as follows.

     private HashSet<String> results = null;
     public List<String> removeInvalidParentheses(String s) {
    	results = new HashSet<>(4096);
    
    	int len = s.length();
    	int hasLeft = s.indexOf("(");
    	int hasRight = s.indexOf(")");
    	if (len <= 0 || (hasLeft == -1 && hasRight == -1)) {
    	    // Case of no parentheses.
    		results.add(s);
    		return new ArrayList<>(results);
    	} else if (hasLeft == -1) {
    	    // No left parentheses.
    		results.add(s.replace(")", ""));
    		return new ArrayList<>(results);
    	} else if (hasRight == -1) {
    	    // No right parentheses.
    		results.add(s.replace("(", ""));
    		return new ArrayList<>(results);
    	}
    
    	char[] str = s.toCharArray();
    	boolean[] remove = new boolean[len];
    	List<Integer> stack = new ArrayList<>(len);
    	dfs(str, remove, stack, 0, len);
    	return new ArrayList<>(results);
    }
    
    public void dfs(char[] str, boolean[] remove, List<Integer> stack, int pos, int len) {
        // End of dfs.
    	if (pos >= len) {
    	    // If there is anything left in the stack, all should be removed.
    		int size = stack.size();
    		for (int i = 0; i < size; i++) {
    			remove[stack.get(i)] = true;
    		}
    		results.add(getResult(str, remove));
    		for (int i = 0; i < size; i++) {
    			remove[stack.get(i)] = false;
    		}
    		return;
    	}
    
    	char c = str[pos];
    	if (c != '(' && c != ')') {
    	    // Chars other than parentheses.
    		dfs(str, remove, stack, pos + 1, len);
    	} else if (c == '(') {
    	    // Left parentheses.
    		stack.add(pos);
    		dfs(str, remove, stack, pos + 1, len);
    		stack.remove(stack.size() - 1);
    	} else if (c == ')') {
    	    // Right parentheses.
    		if (stack.isEmpty()) {
    			// Invalid ones.
    			// Any left parentheses before (including himself) could be removed.
    			// Consecutive left parentheses, just remove one.
    			int i = pos;
    			while (i >= 0) {
    				if (str[i] == ')') {
    				    if (!remove[i]) {
    				        // If it has been note removed before, remove.
    				        // Else ignore.
    					    remove[i] = true;
    					    dfs(str, remove, stack, pos + 1, len);
    					    remove[i] = false;
    					    while (i >= 0) {
    						    if (str[i] == ')') {
    						    	i--;
    						    } else {
    							    break;
    					    	}
    					    }
    				    } else {
    				        i--;
    				    }
    				} else {
    					i--;
    				}
    			}
    		} else {
    		    // There is still something left in the stack. It is a valid parentheses.
    		    // However, this parentheses could be matched to any left parentheses before.
    		    // So we need a loop on that.
    			int size = stack.size();
    			for (int i = 0; i < size; i++) {
    				dfs(str, remove, getList(stack, i), pos + 1, len);
    			}
    		}
    	}
    }
    
    // Generate the result according to str array and remove array.
    public String getResult(char[] str, boolean[] remove) {
    	int len = str.length;
    	StringBuilder sb = new StringBuilder(len);
    	for (int i = 0; i < len; i++) {
    		if (!remove[i]) {
    			sb.append(str[i]);
    		}
    	}
    	return sb.toString();
    }
    
    // Remove an element in the list, generate a new list.
    public List<Integer> getList(List<Integer> stack, int n) {
    	int size = stack.size();
    	List<Integer> result = new ArrayList<>(size);
    	for (int i = 0; i < size; i++) {
    		if (i != n) {
    			result.add(stack.get(i));
    		}
    	}
    	return result;
    }

Log in to reply
 

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