## 题目描述：

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 ).

Examples:

```"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]```

## 解题思路：

```利用评价函数计算字符串中未匹配括号的个数

## Python代码（DFS + 剪枝）：

``````class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
def dfs(s):
mi = calc(s)
if mi == 0:
return [s]
ans = []
for x in range(len(s)):
if s[x] in ('(', ')'):
ns = s[:x] + s[x+1:]
if ns not in visited and calc(ns) < mi:
ans.extend(dfs(ns))
return ans
def calc(s):
a = b = 0
for c in s:
a += {'(' : 1, ')' : -1}.get(c, 0)
b += a < 0
a = max(a, 0)
return a + b

visited = set([s])
return dfs(s)
``````

```通过从输入字符串中移除每一个括号，生成新的字符串加入队列。

## Python代码（BFS）：

``````class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
def isValid(s):
a = 0
for c in s:
a += {'(' : 1, ')' : -1}.get(c, 0)
if a < 0:
return False
return a == 0

visited = set([s])
ans = []
queue = collections.deque([s])
done = False
while queue:
t = queue.popleft()
if isValid(t):
done = True
ans.append(t)
if done:
continue
for x in range(len(t)):
if t[x] not in ('(', ')'):
continue
ns = t[:x] + t[x + 1:]
if ns not in visited:
queue.append(ns)

return ans
``````

BFS也可应用解法I中的剪枝策略：

## Python代码（BFS + 剪枝）：

``````class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
def calc(s):
a = b = 0
for c in s:
a += {'(' : 1, ')' : -1}.get(c, 0)
b += a < 0
a = max(a, 0)
return a + b

visited = set([s])
ans = []
queue = collections.deque([s])
done = False
while queue:
t = queue.popleft()
mi = calc(t)
if mi == 0:
done = True
ans.append(t)
if done:
continue
for x in range(len(t)):
if t[x] not in ('(', ')'):
continue
ns = t[:x] + t[x+1:]
if ns not in visited and calc(ns) < mi:
queue.append(ns)

return ans
``````

Pingbacks已关闭。