Fast Optimized DFS Java solution


  • 0
    I
    // Optimized DFS Solution
    public class Solution {
        public List<String> removeInvalidParentheses(String s) {
            if (s.length() == 0) return new ArrayList<String>(Arrays.asList(""));
            Map<Integer, List<String>> dics = new HashMap<Integer, List<String>>();
            Set<String> visited = new HashSet<String>();
            int[] min = new int[]{Integer.MAX_VALUE};
            char[] str = s.toCharArray();
            helper(dics, str, 0, "", 0, 0, min, 0, visited);
            return dics.get(min[0]);
        }
        private void helper(Map<Integer, List<String>> dics, char[] str, int start, String cur, 
                            int left, int right, int[] min, int delete, Set<String> visited) {
            // Base Cases
            if (visited.contains(cur + delete)) return;
            visited.add(cur + delete);
            if (start == str.length) {
                if (left != right) return;
                if (!dics.containsKey(delete)) dics.put(delete, new ArrayList<String>());
                dics.get(delete).add(cur);
                min[0] = Math.min(min[0], delete);
                return;
            }
            if (left < right) return;
            if (str[start] == '(') {
                helper(dics, str, start + 1, cur + "(", left + 1, right, min, delete, visited);
                helper(dics, str, start + 1, cur, left, right, min, delete + 1, visited);
            } else if (str[start] == ')') {
                helper(dics, str, start + 1, cur + ")", left, right + 1, min, delete, visited);
                helper(dics, str, start + 1, cur, left, right, min, delete + 1, visited);
            } else {
                helper(dics, str, start + 1, cur + str[start], left, right, min, delete, visited);
            }
        }
    }

Log in to reply
 

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