用 Python 编写程序，查找生成有效括号所需的最少删除次数

pythonserver side programmingprogramming更新于 2025/12/12 22:36:17

假设我们有一个字符串 s，其中有括号 '(' , ')' 和小写英文字符。我们必须从任意位置删除最少数量的括号('(' 或 ')')，以使生成的括号字符串有效，并且最终必须返回任何有效字符串。这里，当满足所有这些条件时，括号内的字符串有效 −

字符串为空且仅包含小写字符，或者
字符串可以写成 AB(A 与 B 连接)，其中 A 和 B 是有效字符串，或者
字符串可以写成 (A) 的形式，其中 A 是有效字符串。

因此，如果输入为 s = "m)n(o)p"，则输出为 "mn(o)p"

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

stack := a new list
indexes := a new set
i := 0
对于 s 中的每个 c，执行
- 如果 c 与 '(' 相同，则
  - 将 i 推入堆栈
- 否则，当 c 与 ')' 相同时，则
  - 如果堆栈大小与 0 相同，则
    - 将 i 插入索引
  - 否则，
    - 从堆栈弹出
  - i := i + 1
ret := 空字符串
索引 := 将所有元素存储到索引中
对于 i 在 0 到 s - 1 的大小范围内的情况，执行
- 如果 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))