lc301.删除无效的括号

题目链接

这个题我们考虑用bfs的方法来解决。如何做呢？我们做bfs，上一层level和下一层level之间的关系为：把所有上一层level中的每个元素都拿出来，列举出再删除一个括号后的所有可能情况。（不管删除后是否合法），添加到下一个level中。例如：现在的level是[”())”, “())”]，那么下一层level的元素应该是：1. 对“())”删除一个括号的所有可能为：(),(),((。 2. 对”())”删除一个括号的所有可能为：(),)),()。这六个就是下一个level的全部内容了。但是我们也会发现，就是有重复元素出现的情况，那么我们可以将level中的list换成set就能避免这个重复的发生。至于我们如何检查某个序列是否是一个合法的括号序列，可以维护一个计数器或者用栈的方法实现。另外一个小技巧是，用filter(func, param)函数可以得到param中所有符合条件的元素。其中的判定方法根据func返回的True or False 来决定。

这个算法的时间复杂度是O（2^N），因为在最坏的情况下，表达式中只有左括号，对于每个括号，我们都有两个选项即是删除它还是考虑它。空间复杂度是O（N）。

python:

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:

        def isValid(seq):
            cnt = 0
            for c in seq:
                if c == "(":
                    cnt += 1
                elif c == ")":
                    cnt -= 1
                if cnt < 0:
                    return False  # 一旦中途cnt小于0，就要终止循环，已经出现非法字符（即多余的“）”）
            return cnt == 0

        level = {s}
        while True:
            valid = list(filter(isValid, level))
            if valid:  # 如果当前valid是非空的，说明已经有合法的产生了。
                return valid
            next_level = set()
            for item in level:
                for i in range(len(item)):
                    if item[i] in "()":
                        next_level.add(item[:i]+item[i+1:])
            level = next_level

PREVIOUSlc032.最长有效括号

NEXTmq055.删除无效的括号