301.Remove Invalid Parentheses
Tags: [BFS], [parentheses], [parenthesis], [optimization], [set], [level_by_level]
Com: {fb}
Link: https://leetcode.com/problems/remove-invalid-parentheses/#/description
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())()"]
")(" -> [""]
Solution: BFS, Level By Level:
from collections import deque
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s:
return [""]
result = []
s_set = set([s])
queue = deque([s, None])
while queue:
curr = queue.popleft()
if curr:
if self.is_valid(curr):
result.append(curr)
for i in xrange(len(curr)):
if curr[i] != '(' and curr[i] != ')':
continue
# try to remove the curr parenthesis.
new_s = curr[:i] + curr[i + 1:]
if new_s and new_s not in s_set:
s_set.add(new_s)
queue.append(new_s)
else:
# curr is None, which means the current level finished.
if result:
return result
if queue:
queue.append(None)
return result if result else [""]
def is_valid(self, s):
if not s:
return True
stack = []
for c in s:
if c != '(' and c != ')':
continue
if c == '(':
stack.append(c)
else:
# c == ')'
if not stack:
return False
stack.pop()
return len(stack) == 0
Revelation:
- The reason why using BFS, is that on each level of BFS, we just try to remove one parenthesis, until we find the results, and the BFS guarantees that for example, on the level 4, we find the first valid parentheses string, and if there exist other valid strings, all these valid string must appear on the same level of the BFS. Once we find the valid string on some level, we can just collect the results on that level, and then terminate the BFS. But DFS doesn't have this feature, DFS just search along the path deeper and deeper.
- Af very beginning, I think we don't need use set to remove the duplicate results. But after recognizing there exist the duplicate results. I think we can use the hash set to remove the duplicates.
- And then, I found there exist a lot of duplicates new_s during the BFS, and we don't need to enqueue these duplicates, so then we use a hash set to remove all duplicates, once we remove these duplicates, which also guarantee there is no duplicates in the result container. And because we remove the duplicates during BFS, we also promote the efficiency..
Note:
- Time complexity = O(n^3).
- Explanation of the time complexity: The worst case is that we need the search in BFS level by level until the last level. For each level, we need check the current string is a valid string or not, it takes O(len(curr)), and we iterate all chars in curr, try to remove it and enqueue the new_s, which takes O(len(curr) * len(curr - 1)), because it takes O(len(curr - 1)) to build the new__s. So the time complexity = O((n + n*(n - 1)) + ((n - 1) + (n - 1)*(n - 2)) ...) = O(n^2 + n^3) = O(n^3), but I am not sure this is correct or not?
Another Solution: BFS, Level By Level
Time Limited Exceeded: Brute Force
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s:
return [""]
result_set = set()
result = []
buff = []
self.remove_invalid_parentheses_helper(s, 0, buff, result, result_set)
return result
def remove_invalid_parentheses_helper(self, s, index, buff, result, result_set):
# base case
if index >= len(s):
if self.is_valid(buff):
valid_s = ''.join(buff)
if valid_s in result_set:
return
if not result or len(result[0]) == len(buff):
result_set.add(valid_s)
result.append(''.join(buff))
elif len(buff) > len(result[0]):
result_set.add(valid_s)
result = [''.join(buff)]
return
for i in xrange(index, len(s)):
if s[i] != '(' and s[i] != ')':
buff.append(s[i])
self.remove_invalid_parentheses_helper(s, i + 1, buff, result, result_set)
buff.pop()
else:
# choose s[i]
buff.append(s[i])
self.remove_invalid_parentheses_helper(s, i + 1, buff, result, result_set)
buff.pop()
# not choose s[i]
self.remove_invalid_parentheses_helper(s, i + 1, buff, result, result_set)
def is_valid(self, arr):
if not arr:
return True
stack = []
for c in arr:
if c != '(' and c != ')':
continue
if c == '(':
stack.append(c)
else:
# c == ')'
if not stack:
return False
stack.pop()
return len(stack) == 0
Revelation:
- For each parenthesis, we have two choices, one is choosing it, the other is not choosing it.
Note:
- Time complexity = O(2^n), n is the length of the given string.
Not sure why the below solution doesn't work correctly:
from collections import deque
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s:
return [""]
result = []
if self.is_valid(s):
return [s]
s_set = set([s])
queue = deque([s])
while queue:
curr = queue.popleft()
for i in xrange(len(curr)):
if curr[i] != '(' and curr[i] != ')':
continue
# try to remove the curr[i]
new_s = curr[:i] + curr[i + 1:]
if not new_s or new_s in s_set:
continue
s_set.add(new_s)
queue.append(new_s)
if self.is_valid(new_s):
result.append(new_s)
if result:
print 'curr={}, queue={}'.format(curr, queue)
return result
return result if result else [""]
def is_valid(self, s):
if not s:
return False
stack = []
for c in s:
if c != '(' and c != ')':
continue
if c == '(':
stack.append(c)
else:
# c == ')'
if not stack:
return False
stack.pop()
return len(stack) == 0
if __name__ == '__main__':
print 'Program is working'
s = "(((k()(("
solution = Solution()
print solution.removeInvalidParentheses(s)
print 'Program is end'