在Python中查找最小的删除所需以使括号有效
假设我们有一个字符串s,其中包含括号“(”、“)”和小写英文字母。 我们必须删除最小数量的括号(“(”或“)”,从任何位置)以使结果括号字符串有效,并最终返回任何有效字符串。 在这里,当满足以下所有条件时,括号字符串才有效 −
- 该字符串为空并且仅包含小写字符,或
-
该字符串可以写成AB(与B连接的A),其中A和B是有效字符串,或
-
该字符串可以写成(A)的形式,其中A是有效字符串。
所以,如果输入是s =“m) n(o)p”,则输出将是“mn(o)p”
为了解决这个问题,我们将按照以下步骤进行 −
- stack:=新列表
-
索引:=新设置
-
i:=0
-
对于s中的每个c,进行
- 如果c与“(”相同,则
- 将i推入stack
- 否则,当c与“)”相同时,则
- 如果堆栈大小与0相同,则
-
将i插入索引
-
否则,
-
从堆栈弹出
-
i:=i + 1
- 如果c与“(”相同,则
-
ret:=空字符串
-
索引:=将所有元素存储到索引中
-
对于i在0到s的大小的范围内,执行
- 如果i不在索引中,则
- ret:=ret + s[i]
- 如果i不在索引中,则
- 返回 ret
示例
让我们看一下以下实现,以更好地理解−
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