寻找在 Python 中制作有效括号所需的最小删除的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个带有括号 '(' , ')' 和小写英文字符的字符串 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

以上是 寻找在 Python 中制作有效括号所需的最小删除的程序 的全部内容， 来源链接： utcz.com/z/357472.html

回到顶部