# A 68ms Python Solution by BFS and some optimization

• ``````class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
degree = self.validDegree(s)
if degree == 0:
return [s]
index = 0
while index < len(s) and s[index] == ')':
index += 1
initIndex = index
preIndex = index
count = 0
while index < len(s):
if s[index] == '(':
count += 1
index += 1
elif s[index] == ')':
count -= 1
index += 1
if count < 0:
count = 0
while index < len(s) and s[index] != '(':
index += 1
preIndex = index
else:
index += 1
leftPart = self.cur(s[initIndex:preIndex], set([]), ')', self.validDegree(s[initIndex:preIndex]))
rightPart = self.cur(s[preIndex:], set([]), '(', self.validDegree(s[preIndex:]))
result = []
for r1 in leftPart:
for r2 in rightPart:
result.append(r1+r2)
return result
def cur(self, s, oldStr, validChr, degree):
if degree == 0:
if self.validDegree(s) == 0:
return [s]
else:
return []
else:
result = []
for i, c in enumerate(s):
if c == validChr:
nextStr = s[0:i]+s[i+1:]
if nextStr not in oldStr:
tmpResult = self.cur(nextStr, oldStr, validChr, degree - 1)
for res in tmpResult:
result.append(res)
return result
def validDegree(self, s):
count = 0
stack = []
for c in s:
if c == '(':
stack.append(c)
elif c == ')':
if stack != []:
stack.pop()
else:
count += 1
count += len(stack)
return count``````

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