目录

0301:删除无效的括号(★★)

力扣第 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