301. 删除无效的括号

ppx

2021-08-26

leetcode

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 ')'.
There will be at most 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
}