# Short Python BFS

• Solution 1

Being lazy and using `eval` for checking:

``````def removeInvalidParentheses(self, s):
level = {s}
while True:
valid = []
for s in level:
try:
eval('0,' + filter('()'.count, s).replace(')', '),'))
valid.append(s)
except:
pass
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
``````

Update: Meh, ok, checking it myself isn't that much longer, and it's three times as fast:

Solution 2

``````def removeInvalidParentheses(self, s):
def isvalid(s):
ctr = 0
for c in s:
if c == '(':
ctr += 1
elif c == ')':
ctr -= 1
if ctr < 0:
return False
return ctr == 0
level = {s}
while True:
valid = filter(isvalid, level)
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
``````

Solution 3

Just a mix of the above two.

``````def removeInvalidParentheses(self, s):
def isvalid(s):
try:
eval('0,' + filter('()'.count, s).replace(')', '),'))
return True
except:
pass
level = {s}
while True:
valid = filter(isvalid, level)
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
``````

Solution 4

Yet another way to do `isvalid`.

``````def removeInvalidParentheses(self, s):
def isvalid(s):
s = filter('()'.count, s)
while '()' in s:
s = s.replace('()', '')
return not s
level = {s}
while True:
valid = filter(isvalid, level)
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}``````

• You have never stopped to amaze me

• The king of clean and amazing code

• @StefanPochmann amazing, so clean and pythonic

• Meh, what a noob code, could've made Solution 2 shorter like this :-)

``````    def isvalid(s):
ctr = 0
for c in s:
ctr += (c == '(') - (c == ')')
if ctr < 0:
return False
return ctr == 0
``````

Another way would be `ctr += ('()'.find(c) + 2) % 3 - 1` but that's not just complicated but also longer and slower...

I quite like `filter('()'.count, s)`, though, and don't even remember having done that :-P

• What if input is like `'a)b)c)d)e)f)g)h)i)j)k)l)m)n)o)p)(((((((((((((((((((('`. BFS above will search too many useless states and get stuck.

• This post is deleted!

• Really Nice and clean code ! thank you for sharing

• AMAZING code!

• I improve your solution 2 a little bit. Instead of check whether `s` is invalid, we can also count the # of unmatched parenthesizes, either left or right. Assume there are k such parenthesizes, we know that we need to remove k of them. In this case, the BFS can go straight to level k and thus a little bit faster.

``````class Solution(object):
def removeInvalidParentheses(self, s):

def countInvalidParentheses(string):
left_ctr = right_ctr = 0
for c in string:
if c == '(':
left_ctr += 1
elif c == ')':
if left_ctr > 0:
left_ctr -= 1
else:
right_ctr += 1
return left_ctr + right_ctr

level = {s}
for _ in range(countInvalidParentheses(s)):
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}

return filter(lambda string: countInvalidParentheses(string) > 0, level)
``````

I am surprised it can pass the auto grader. I agree with @Misaka-10032. This solution will be very slow when # of parentheses is large, e.g. `)))))))))))))))))))))`

• how do you analyze the time complexity of this code

• @StefanPochmann
Is this the best we can achieve for this problem ?

How do we calculate time complexity ? This is how I am interpreting it, when length of input string is N:

Time complexity for isvalid function is n.

For level 1, one string of length N, and hence N.
For level 2, N strings with length N-1, and hence complexity N*(N-1)
For level 3, N*(N-1) strings with each length N-2, and hence time complexity N*(N-1)*N(N-2) and so on.

Does that mean complexity is O(N^N) ?

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