Java DFS solution, easy concept, yet 119ms. who knows why?


  • 0
    Y
    public List<String> removeInvalidParentheses(String s) {
        // 7:41pm - 8:20pm
        // DFS solution:
        // scan left to right, time complexity O(n^3)
    	Set<String> result = new HashSet<String>(); 
    	//System.out.println("size:" + result.size());
        removeInvalidParenthesesHelper(s.toCharArray(), 0, 0, new StringBuilder(), result);
        Map<Integer, List<String>> resultByLength = new HashMap<Integer, List<String>>();
        int maxLen = 0;
        for (String ss : result) {
        	if (! resultByLength.containsKey(ss.length())) {
        		resultByLength.put(ss.length(), new ArrayList<String>());
        	}
        	resultByLength.get(ss.length()).add(ss);
        	if (ss.length() > maxLen) {
        		maxLen = ss.length();
        	}
        }
        return resultByLength.get(maxLen);
    }
    
    private void removeInvalidParenthesesHelper(char[] array, int numLeft, int curr, StringBuilder sb, Set<String> result) {
        // numLeft for opening left brackets that are unresolved
        if (curr == array.length) {
            if (numLeft == 0) {
                result.add(sb.toString());
            }
            return;
        }
        if (array[curr] == '(') {
            // skip it
            removeInvalidParenthesesHelper(array, numLeft, curr + 1, sb, result); 
            // take it
            sb.append(array[curr]);
            removeInvalidParenthesesHelper(array, numLeft + 1, curr + 1, sb, result);
            sb.deleteCharAt(sb.length()-1);
        } else if (array[curr] == ')') {
            if (numLeft > 0) {
                // take it
                sb.append(array[curr]);
                removeInvalidParenthesesHelper(array, numLeft - 1, curr + 1, sb, result);
                sb.deleteCharAt(sb.length()-1);                
            }
            // skip it
            removeInvalidParenthesesHelper(array, numLeft, curr + 1, sb, result);
        } else {
            // take it
            sb.append(array[curr]);
            removeInvalidParenthesesHelper(array, numLeft, curr + 1, sb, result);   
            sb.deleteCharAt(sb.length()-1); 
        }
    }

Log in to reply
 

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