寻找在 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
热门推荐
10 祝女儿简短祝福语大全
11 大学新年祝福语简短创意
12 元旦适合的祝福语简短
13 朋友出远门祝福语简短
14 初六简短的祝福语
15 祝男孩生日祝福语简短
16 同事调离的祝福语简短
17 拜年红包的祝福语简短
18 妈妈生日祝福语简短励志