[LeetCode] 301. Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Thought process:
BFS:

1. Graph definition:
1. Vertex: a candidate string.
2. Edge: two strings s1 and s2 have an edge if s1 equals s2 with one parenthesis deleted.
2. Put string into a queue.
3. For the current size of the queue, poll a string from the queue.
1. Iterate through the string. For each character, remove it, and check if the parentheses are valid.
2. If so, iterate over current level and return the result.
3. If not, offer the new string to the queue.

Solution 1 (BFS):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

class Solution { public List<String> removeInvalidParentheses(String s) { List<String> list = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); queue.offer(s); Set<String> visited = new HashSet<>(); visited.add(s); boolean found = false; while (!found && !queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String str = queue.poll(); if (isValid(str)) { list.add(str); found = true; continue; } for (int j = 0; j < str.length(); j++) { if (str.charAt(j) != '(' && str.charAt(j) != ')') { continue; } String child = str.substring(0, j) + str.substring(j + 1); if (!visited.contains(child)) { queue.offer(child); visited.add(child); } } } } return list; } private boolean isValid(String s) { int open = 0; for (char c : s.toCharArray()) { if (c == '(') { open++; } else if (c == ')') { if (open == 0) { return false; } open--; } } return open == 0; } }

Time complexity:
Say the string's length is n. For every character, the choice is to keep or remove. So there are 2^n total states to check. Check if a string is valid is O(1). So the overall time complexity is O(2^n).

There is another solution using DFS. Calculate the number of invalid parentheses of the original string. Iterate through the string. Remove each character and DFS if the number of invalid parentheses decreases.
This solution is based on the fact that if we're on the right path to the optimal string, the number of invalid parentheses must always decrease.

Solution 2 (DFS):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

class Solution { public List<String> removeInvalidParentheses(String s) { List<String> list = new ArrayList<>(); Set<String> visited = new HashSet<>(); removeInvalidParentheses(s, numberOfInvalid(s), list, visited); return list; } private void removeInvalidParentheses(String s, int invalid, List<String> list, Set<String> visited) { if (invalid == 0) { list.add(s); return; } for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != '(' && s.charAt(i) != ')') { continue; } String child = s.substring(0, i) + s.substring(i + 1, s.length()); if (!visited.contains(child)) { visited.add(child); int next = numberOfInvalid(child); if (next < invalid) { removeInvalidParentheses(child, next, list, visited); } } } } private int numberOfInvalid(String s) { int open = 0; int close = 0; for (char c : s.toCharArray()) { if (c == '(') { open++; } else if (c == ')') { if (open == 0) { close++; } else { open--; } } } return open + close; } }

Time complexity:
In the worst case, I could have some input like "))))))))", where I need to search through the entire string. The good thing is duplicates will be pruned by the hash set. Calculating mis-match takes O(n). So the overall time complexity is O(n^2).