如果只需要找一个存在的解：（使用栈即可）
O(N^2)
class Solution():
def removeInvalidParentheses(self, s):
if not s:
return
stack = []
for i, token in enumerate(s):
if token == ")" and stack and stack[-1][1] == "(":
stack.pop()
elif token in ('(',')'):
stack.append((i,token))
else:
continue
s = list(s)
while stack:
s.pop(stack.pop()[0])
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 ).
Example 1:
Input: "()())()"
Output: ["()()()", "(())()"]
Solution
- BFS
Time: O(2^N)
Space: O(N!) 最坏情况(搜索树最宽的一层)
from collections import deque
class Solution:
def is_valid(self,s):
left = 0
for ch in s:
if ch == '(':
left +=1
if ch == ')':
if left ==0 :
return False
left -= 1
return left == 0
def removeInvalidParentheses(self, s: str) -> List[str]:
queue = [s]
res = []
found = False
visited = set()
while len(queue) > 0:
candi = queue.pop(0)
if self.is_valid(candi):
res.append(candi)
found = True
if found is False:
for i in range(len(candi)):
if candi[i] == '(' or candi[i]==')':
new_candi = candi[:i]+candi[i+1:]
if new_candi not in visited:
queue.append(new_candi)
visited.add(new_candi)
return res
- DFS
Time O(2^N)
Space O(N)
class Solution:
def removeInvalidParentheses(self, s):
res = []
left, right = self._LeftRightCount(s)
self._dfs(s, left, right, 0, res)
return res
def _dfs(self, s, left, right, start, res):
if left==0 and right==0:
if self._isvalid(s):
res.append(s)
return
for i in xrange(start, len(s)):
if i > start and s[i] == s[i-1]:
continue
if s[i] == '(':
self._dfs(s[:i]+s[i+1:], left-1, right, i, res)
if s[i] == ')':
self._dfs(s[:i]+s[i+1:], left, right-1, i, res)
def _isvalid(self, s):
left, right = self._LeftRightCount(s)
return left==0 and right==0
def _LeftRightCount(self, s):
left = right = 0
for ch in s:
if ch == '(':
left += 1
if ch == ')':
if left > 0:
left -= 1
else:
right += 1
return left, right
