在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))