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: [""]
Solutions
DFS+剪枝，写不出来，这辈子是写不出来了。
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
res = []
# avoid same result
self.visited = set([s])
self.dfs(s, self.invalid(s), res)
return res
def dfs(self, s, n, res):
if n == 0:
res.append(s)
return
for i in range(len(s)):
if s[i] in ['(', ')']:
s_new = s[:i] + s[i+1:]
if not s_new in self.visited and self.invalid(s_new) < n:
self.visited.add(s_new)
self.dfs(s_new, self.invalid(s_new), res)
def invalid(self, s):
# invalid part of left and right parentheses
plus = minus = 0
memo = {"(": 1, ")": -1}
for c in s:
plus += memo.get(c, 0)
minus += 1 if plus < 0 else 0
plus = max(0, plus)
return plus + minus
# Runtime: 188 ms, faster than 53.01% of Python online submissions for Remove Invalid Parentheses.
# Memory Usage: 11.9 MB, less than 63.16% of Python online submissions for Remove Invalid Parentheses.