# lc301. Remove Invalid Parentheses

Contents

Given a string `s` that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

Example 1:

 ``````1 2 `````` ``````Input: s = "()())()" Output: ["(())()","()()()"] ``````

Example 2:

 ``````1 2 `````` ``````Input: s = "(a)())()" Output: ["(a())()","(a)()()"] ``````

Example 3:

 ``````1 2 `````` ``````Input: s = ")(" Output: [""] ``````

Constraints:

• `1 <= s.length <= 25`
• `s` consists of lowercase English letters and parentheses `'('` and `')'`.
• There will be at most `20` parentheses in `s`.

###### 解题思路：

1. 如果父节点已经是合法字符串，则无需再考虑任何子节点。
2. 如果有一个节点已经是合法字符串，则其它所有结果都只可能出现在和这个节点同一层（为了确保minimal removal）。
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 `````` ``````class Solution(object): def removeInvalidParentheses(self, s): """ :type s: str :rtype: List[str] """ def delOne(string): out=set() for i in range(len(string)): tmp=list(string) tmp.pop(i) out.add(''.join(tmp)) return out def getNextLevel(level): """ :type level: set """ nextlevel=set() for _ in level: for __ in delOne(_): nextlevel.add(__) return nextlevel def isValid(string): count=0 for _ in string: if _=='(': count+=1 elif _==')': count-=1 if count<0: return False if count==0: return True else: return False level=[s] length=len(s) while True: current_ans=[] #print(current_ans,level) for _ in level: if isValid(_)==True: current_ans.append(_) else: pass if len(current_ans)!=0: break else: if length>1: level=getNextLevel(level) length-=1 else: current_ans=[""] break return current_ans ``````