Python程序：查找使括号有效所需的最少删除次数

假设我们有一个包含括号 '('、')' 和小写英文字母的字符串 s。我们必须删除最小数量的括号（'(' 或 ')'，从任何位置）以便生成的括号字符串有效，并最终返回任何有效的字符串。这里的括号字符串在满足所有这些条件时才是有效的：

  • 字符串为空且仅包含小写字符，或者

  • 字符串可以写成 AB（A 与 B 连接）的形式，其中 A 和 B 是有效的字符串，或者

  • 字符串可以写成 (A) 的形式，其中 A 是一个有效的字符串。

因此，如果输入类似于 s = "m)n(o)p"，则输出将是 "mn(o)p"

为了解决这个问题，我们将遵循以下步骤：

  • stack := 新建一个列表

  • indexes := 新建一个集合

  • i := 0

  • 对于s中的每个字符c，执行：

    • 如果c 等于 '('，则

      • 将i压入栈中

    • 否则，如果c 等于 ')'，则

      • 如果栈的大小等于 0，则

        • 将i插入到indexes中

      • 否则，

        • 从栈中弹出

      • i := i + 1

  • ret := 空字符串

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

  • 对于从0到s的大小-1的范围内的每个i，执行：

    • 如果i不在indexes中，则

      • 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

更新于：2021年10月7日

浏览量：297

启动您的职业生涯

通过完成课程获得认证

开始
广告