寻找在 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
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下