Python 中两个有效括号字符串的最大嵌套深度

pythonserver side programmingprogramming更新于 2025/11/14 16:44:17

假设我们有一个字符串，当且仅当该字符串由"("和")"组成时，该字符串才是有效的括号字符串(表示为 VPS)字符，并且满足这些属性 −

它是空字符串，或者
它可以写成 AB，其中 A 和 B 是 VPS，或者
它可以写成 (A)，其中 A 是 VPS。

我们还可以定义任何 VPS S 的嵌套深度depth(S)，如下所示 −

depth("") = 0
depth(A + B) = 深度(A)、深度(B) 的最大值，其中 A 和 B 是 VPS
depth("(" + A + ")") = 1 + 深度(A)，其中 A 是VPS。

如果我们有一个 VPS 序列，我们必须将其拆分为两个不相交的子序列 A 和 B，使得 A 和 B 是 VPS(并且 A 的长度 + B 的长度 = 序列的长度)。现在，如果我们选择任何这样的 A 和 B，使得 max(depth(A),depth(B)) 是最小可能值。然后我们必须找到一个答案数组(长度为 seq)，对 A 和 B 的选择进行编码:如果 seq[i] 是 A 的一部分，则 answer[i] = 0，否则 answer[i] = 1。

因此，如果输入为"()(())()"，则输出为 [1,1,1,0,1,0,1,1]

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

n := seq 的长度，res := 长度为 n 的 0 数组
c1, c2 := 0, 0
对于范围为 0 到 n 的 i – 1
- 如果 seq[i] = ‘(’
  - 如果 c1 < c2，则将 c1 增加 1，否则将 c2 增加 1 且 res[i] := 1
- 否则
  - 如果 c1 > c2，则将 c1 减少 1，否则将 c2 减少 1 且 res[i]:= 1
返回 res

让我们看看下面的实现以便更好地理解 −

示例

class Solution(object):
   def maxDepthAfterSplit(self, seq):
      n = len(seq)
      res = [0] *n
      c1,c2= 0,0
      for i in range(n):
         if seq[i] == '(':
            if c1<c2:
               c1+=1
         else:
            c2+=1
            res[i]=1
      else:
         if c1>c2:
            c1-=1
         else:
            c2-=1
            res[i]=1
   return res
ob = Solution()
print(ob.maxDepthAfterSplit("()(())()"))