在Python中查找最小的删除所需以使括号有效

在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

  • ret:=空字符串

  • 索引:=将所有元素存储到索引中

  • 对于i在0到s的大小的范围内,执行

    • 如果i不在索引中,则
      • ret:=ret + s[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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程