0%

leetcode Remove Invalid Parentheses

leetcode Remove Invalid Parentheses

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:

题意:

给定一串括号组成的字符串(可能 有其他字符),要求你在去除最少的括号数情况下,使其合法。输出所有结果

思路:

方法一 BFS:

枚举去除的点,当找到后停止BFS树的扩展(因为要去除最少括号,所以即使有其他的结果,也一定在同一层)

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
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s: return ['']
q, ans, vis = [s], [], set([s])
found = False
while q:
cur = q.pop(0)
if self.isValidParentheses(cur):
found = True
ans.append(cur)
elif not found:
for i in xrange(len(cur)):
if cur[i] == '(' or cur[i] == ')':
t = cur[:i] + cur[i + 1:]
if t not in vis:
q.append(t)
vis.add(t)
return ans

def isValidParentheses(self, s):
cnt = 0
for c in s:
if c == '(':
cnt += 1
elif c == ')':
if cnt == 0: return False
cnt -= 1
return cnt == 0

更简洁的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s: return ['']
q = {s}
while q:
ans = filter(self.isValidParentheses,q)
if ans: return ans
q = {cur[:i] + cur[i + 1:] for cur in q for i in xrange(len(cur))}

def isValidParentheses(self, s):
cnt = 0
for c in s:
if c == '(':
cnt += 1
elif c == ')':
if cnt == 0: return False
cnt -= 1
return cnt == 0

 

方法二: DFS

统计左右括号能删的个数,进行DFS。

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
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s: return ['']
left_remove = right_remove = 0
for c in s:
if c == '(':
left_remove += 1
elif c == ')':
if left_remove:
left_remove -= 1
else:
right_remove += 1

ans = set()
self.dfs(0, left_remove, right_remove, 0, '', s, ans)
return list(ans)

def dfs(self, index, left_remove, right_remove, left_pare, cur, s, ans):
if left_remove < 0 or right_remove < 0 or left_pare < 0: return
if index == len(s):
if left_remove == right_remove == left_pare == 0:
ans.add(cur)
return

if s[index] == '(':
self.dfs(index + 1, left_remove - 1, right_remove, left_pare, cur, s, ans)
self.dfs(index + 1, left_remove, right_remove, left_pare + 1, cur + s[index], s, ans)
elif s[index] == ')':
self.dfs(index + 1, left_remove, right_remove - 1, left_pare, cur, s, ans)
self.dfs(index + 1, left_remove, right_remove, left_pare - 1, cur + s[index], s, ans)
else:
self.dfs(index + 1, left_remove, right_remove, left_pare, cur + s[index], s, ans)


请我喝杯咖啡吧~