寻找在 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