题目

LeetCode.301.删除无效的括号（困难）

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = “()())()”
输出：[“(())()”,”()()()”]
示例 2：

输入：s = “(a)())()”
输出：[“(a())()”,”(a)()()”]
示例 3：

输入：s = “)(“
输出：[“”]

提示：

1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号

题解

解法1：广度优先搜索

思路

寻找最短路径考虑使用广度优先搜索。

不知道删除哪个括号，就把所有的括号都依次删除试一遍。
一直试到发现了可以形成有效括号，不用再试了。

怎么判断是否可以形成有效括号？

左括号个数与右括号个数相等。

BFS下一层是什么？

初始时，s作为第一层。
删除s中的一个括号，得到下一层的字符串。
- 不知道删除s中的哪个括号，就把所有位置的括号都试着删除一次。
- 删除一个括号后，剩余字符串可能会重复，存储时可以添加到HashSet里去重。

BFS怎么发现需要删除最少的括号数？

每一层都会针对所有可能的有效括号字符串删除一个字符得到新的字符串集合。
如果新的字符串集合中有可以形成有效括号的字符串，BFS已经遍历的层数就是需要删除的最少括号数。

import java.lang.StringBuilder

class Solution {
    fun removeInvalidParentheses(s: String): List<String> {
        var level = mutableSetOf(s)
        while (level.isNotEmpty()) {
            val validResult = level.filter { it.hasValidBrackets() }
            if (validResult.isNotEmpty()) return validResult
            val nextLevel = mutableSetOf<String>()
            level.forEach { str ->
                for (i in str.indices) {
                    if (str[i] == '(' || str[i] == ')') {
                        val newString = StringBuilder(str).deleteCharAt(i).toString()
                        nextLevel.add(newString)
                    }
                }
            }
            level = nextLevel
        }
        return level.toList()
    }

    /**
     * 是否有有效的括号
     */
    private fun String.hasValidBrackets(): Boolean {
        val s = this
        var leftBracketCount = 0
        for (c in s) {
            when (c) {
                '(' -> leftBracketCount++
                ')' -> {
                    if (leftBracketCount == 0) return false
                    leftBracketCount--
                }
            }
        }
        return leftBracketCount == 0
    }
}

解法2：深度优先搜索

思路

找出不合法的左括号个数和右括号个数。
利用DFS不断删除左括号或者右括号，直到不合法括号个数为0。
检验删除后的括号串是否合法。

剪枝优化

相邻两个字符相同的话，删除这两个字符所得到的字符串是一样的，处理就重复了。

class Solution {
    data class InvalidBracketCount(val left: Int, val right: Int)

    fun removeInvalidParentheses(s: String): List<String> {
        val invalidBracketCount = s.invalidBracketCount
        val result = mutableSetOf<String>()
        dfs(s, 0, invalidBracketCount.left, invalidBracketCount.right, result)
        return result.toList()
    }

    private fun dfs(s: String, start: Int, left: Int, right: Int, result: MutableSet<String>) {
        if (left == 0 && right == 0) {
            if (s.hasValidBrackets()) {
                result.add(s)
            }
            return
        }
        for (i in start until s.length) {
            // 相邻两个字符相同的话，删除这两个字符所得到的字符串是一样的，处理就重复了
            if (i > start && s[i] == s[i - 1]) continue
            if (left > 0 && s[i] == '(') {
                val newString = s.removeRange(i, i + 1)
                dfs(newString, i, left - 1, right, result)
            }
            if (right > 0 && s[i] == ')') {
                val newString = s.removeRange(i, i + 1)
                dfs(newString, i, left, right - 1, result)
            }
        }
    }

    private val String.invalidBracketCount: InvalidBracketCount
        get() {
            val s = this
            var left = 0
            var right = 0
            for (c in s) {
                when (c) {
                    '(' -> left++
                    ')' -> {
                        if (left == 0) right++
                        else left--
                    }
                }
            }
            return InvalidBracketCount(left, right)
        }

    /**
     * 是否有有效的括号
     */
    private fun String.hasValidBrackets(): Boolean {
        val s = this
        var leftBracketCount = 0
        for (c in s) {
            when (c) {
                '(' -> leftBracketCount++
                ')' -> {
                    if (leftBracketCount == 0) return false
                    leftBracketCount--
                }
            }
        }
        return leftBracketCount == 0
    }
}