0301：删除无效的括号（★★）

2015-10-28 约 319 字预计阅读 1 分钟次阅读

力扣第 301 题

题目

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

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

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

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

分析

可以直接递归求删除 k 个括号的序列集合
假如其中有符合的序列，k 即是最小，返回所有符合的序列即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def check(s):
            A = [1 if c=='(' else -1 for c in s if c in '()']
            P = list(accumulate([0]+A))
            return min(P)==P[-1]==0
        Q = [s]
        while True:
            res = [s for s in Q if check(s)]
            if res:
                return res
            Q = {s[:i]+s[i+1:] for s in Q for i,c in enumerate(s) if c in '()'}
        return res

154 ms

目录

0301：删除无效的括号（★★）

题目

分析

解答