-
-
Notifications
You must be signed in to change notification settings - Fork 5.7k
/
301.Remove Invalid Parentheses.go
69 lines (65 loc) · 1.26 KB
/
301.Remove Invalid Parentheses.go
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
package leetcode
var (
res []string
mp map[string]int
n int
length int
maxScore int
str string
)
func removeInvalidParentheses(s string) []string {
lmoves, rmoves, lcnt, rcnt := 0, 0, 0, 0
for _, v := range s {
if v == '(' {
lmoves++
lcnt++
} else if v == ')' {
if lmoves != 0 {
lmoves--
} else {
rmoves++
}
rcnt++
}
}
n = len(s)
length = n - lmoves - rmoves
res = []string{}
mp = make(map[string]int)
maxScore = min(lcnt, rcnt)
str = s
backtrace(0, "", lmoves, rmoves, 0)
return res
}
func backtrace(i int, cur string, lmoves int, rmoves int, score int) {
if lmoves < 0 || rmoves < 0 || score < 0 || score > maxScore {
return
}
if lmoves == 0 && rmoves == 0 {
if len(cur) == length {
if _, ok := mp[cur]; !ok {
res = append(res, cur)
mp[cur] = 1
}
return
}
}
if i == n {
return
}
if str[i] == '(' {
backtrace(i+1, cur+string('('), lmoves, rmoves, score+1)
backtrace(i+1, cur, lmoves-1, rmoves, score)
} else if str[i] == ')' {
backtrace(i+1, cur+string(')'), lmoves, rmoves, score-1)
backtrace(i+1, cur, lmoves, rmoves-1, score)
} else {
backtrace(i+1, cur+string(str[i]), lmoves, rmoves, score)
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}