Given a string s
that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return all the possible results. You may return the answer in any order.
Example 1:
Input: s = "()())()"
Output: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")("
Output: [""]
Constraints:
1 <= s.length <= 25
s
consists of lowercase English letters and parentheses '('
and ')'
.20
parentheses in s
.// 判断字符串是否是合法的左右括号
func getParenthesesNums(s string) (left, right int, isValid bool) {
isValid = true
for i := range s {
if s[i] == '(' {
left++
} else if s[i] == ')' {
if left != 0 {
left--
} else {
right++
}
// 任意时刻,一定是右括号小于等于左括号,否则就是不合法的,
// 但是需要计算非法左右括号数,所以循环继续,比如()())(
if right > left {
isValid = false
}
}
}
return
}
func dfs(s string, start, left int, right int, res *[]string) {
if 0 == left && 0 == right {
// 判断是否字符串是否合法
if _, _, isValid := getParenthesesNums(s); isValid {
*res = append(*res, s)
}
return
}
fmt.Println(left, right)
// 如果需要删除的左括号和右括号不为零,就遍历字符串,找到可以删除的位置
for i := start; i < len(s); i++ {
if i != start && s[i] == s[i-1] {
//说明存在括号重复,只删第一个,来处理就行
continue
}
if s[i] == '(' && left > 0 {
cur := string(append([]byte(s[:i]), s[i+1:]...))
// fmt.Println(s, cur)
dfs(cur, i, left-1, right, res)
}
if s[i] == ')' && right > 0 {
cur := string(append([]byte(s[:i]), s[i+1:]...))
// fmt.Println(cur)
dfs(cur, i, left, right-1, res)
}
}
return
}
func removeInvalidParentheses(s string) []string {
// 1. 找出不合法的左括号和右括号数
// 从左往右遍历的时候,在任意时刻,右括号数一定要小于左括号数
left, right, _ := getParenthesesNums(s)
// 2. 从第0位开始扫描,逐个去尝试移除括号之后的字符串中的括号是否合法
var res = make([]string, 0)
dfs(s, 0, left, right, &res)
return res
}
func dfs(s string, start, left int, right int, res *[]string) {
if 0 == left && 0 == right {
// 判断是否字符串是否合法
if _, _, isValid := getParenthesesNums(s); isValid {
*res = append(*res, s)
}
return
}
fmt.Println(left, right)
// 如果需要删除的左括号和右括号不为零,就遍历字符串,找到可以删除的位置
for i := start; i < len(s); i++ {
if i != start && s[i] == s[i-1] {
//说明存在括号重复,只删第一个,来处理就行
continue
}
if s[i] == '(' && left > 0 {
cur := string(append([]byte(s[:i]), s[i+1:]...))
// fmt.Println(s, cur)
dfs(cur, i, left-1, right, res)
}
if s[i] == ')' && right > 0 {
cur := string(append([]byte(s[:i]), s[i+1:]...))
// fmt.Println(cur)
dfs(cur, i, left, right-1, res)
}
}
return
}
// 判断字符串是否是合法的左右括号
func getParenthesesNums(s string) (left, right int, isValid bool) {
isValid = true
for i := range s {
if s[i] == '(' {
left++
} else if s[i] == ')' {
if left != 0 {
left--
} else {
right++
}
// 任意时刻,一定是右括号小于等于左括号,否则就是不合法的,
// 但是需要计算非法左右括号数,所以循环继续,比如()())(
if right > left {
isValid = false
}
}
}
return
}