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: ["()()()", "(())()"]
Example 2:
Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")("
Output: [""]
My code:
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s:
return [s]
ans =[]
l, r = self.rl(s)#Get the number mismatch for '(' and ')'
print(l,r)
self.removehelper(s, 0, l, r, ans)
return ans
def removehelper(self, s, start, l, r, ans):
if l ==0 and r ==0:#When l and r is same, then it's done
print('path s', s)
if self.isValid(s):
print('valid s',s)
ans.append(str(s))
return
for i in range(start, len(s)):
#print(s)
if (i!= start and s[i]==s[i-1]): continue#If same, we can remove both, save time
#print('the current i',i, s)
curr = s[0:i]+s[i+1:]
#print('curr', curr)
if (r>0 and s[i]==')'):
self.removehelper(curr, i, l, r-1, ans )
elif (l>0 and s[i]=='('):
self.removehelper(curr, i, l-1, r, ans)
def rl(self, s):
l,r = 0,0
for char in s:
if char =='(':
l +=1
if char ==')':
if l ==0:
r +=1
else:
l -=1
return l, r
def isValid(self,s):
#Check now s is valid or not
count = 0
for i in s:
if i == '(':
count +=1
if i == ')':
count -=1
if count <0:
return False
return count ==0Solution: https://leetcode.com/problems/remove-invalid-parentheses/