寻找在 Python 中制作有效括号所需的最小删除的程序
假设我们有一个带有括号'(',')'和小写英文字符的字符串s。我们必须从任何位置删除最小数量的括号('('或')',从任何位置),以便得到的括号字符串是有效的,并且必须最终返回任何有效的字符串。此处括号字符串在满足所有这些条件时有效-
字符串为空且仅包含小写字符,或
字符串可以写成AB(A与B连接),其中A和B是有效字符串,或
字符串可以写成(A)的形式,其中A是有效字符串。
因此,如果输入类似于s="m)n(o)p",那么输出将是"mn(o)p"
示例
让我们看看以下实现以获得更好的理解-
def solve(s): stack = [] indexes = set() i = 0 for c in s: if c == '(': stack.append(i) elif c == ')': if len(stack) == 0: indexes.add(i) else: stack.pop() i += 1 ret = '' indexes = indexes.union(stack) for i in range(len(s)): if i not in indexes: ret += s[i] return ret s = "m)n(o)p" print(solve(s))
输入
"m)n(o)p"输出结果
mn(o)p