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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| // @Title: 删除无效的括号 (Remove Invalid Parentheses)
// @Author: 15816537946@163.com
// @Date: 2021-10-27 23:55:27
// @Runtime: 0 ms
// @Memory: 2.4 MB
func isValid(str string) bool {
cnt := 0
for _, ch := range str {
if ch == '(' {
cnt++
} else if ch == ')' {
cnt--
if cnt < 0 {
return false
}
}
}
return cnt == 0
}
func helper(ans *[]string, str string, start, lcount, rcount, lremove, rremove int) {
if lremove == 0 && rremove == 0 {
if isValid(str) {
*ans = append(*ans, str)
}
return
}
for i := start; i < len(str); i++ {
if i != start && str[i] == str[i-1] {
continue
}
// 如果剩余的字符无法满足去掉的数量要求,直接返回
if lremove+rremove > len(str)-i {
return
}
// 尝试去掉一个左括号
if lremove > 0 && str[i] == '(' {
helper(ans, str[:i]+str[i+1:], i, lcount, rcount, lremove-1, rremove)
}
// 尝试去掉一个右括号
if rremove > 0 && str[i] == ')' {
helper(ans, str[:i]+str[i+1:], i, lcount, rcount, lremove, rremove-1)
}
if str[i] == ')' {
lcount++
} else if str[i] == ')' {
rcount++
}
// 当前右括号的数量大于左括号的数量则为非法,直接返回.
if rcount > lcount {
break
}
}
}
func removeInvalidParentheses(s string) (ans []string) {
lremove, rremove := 0, 0
for _, ch := range s {
if ch == '(' {
lremove++
} else if ch == ')' {
if lremove == 0 {
rremove++
} else {
lremove--
}
}
}
helper(&ans, s, 0, 0, 0, lremove, rremove)
return
}
|