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

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

假设我们有一个字符串，当且仅当该字符串仅由“（”和“）”字符组成且满足这些属性时，该字符串才是有效的括号字符串（表示为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 + depth(A)，其中A是VPS。

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

因此，如果输入类似于“（()（()）()”），则输出将为[1,1,1,0,1,0,1,1,1]

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

n：= seq的长度，res：=长度为n的0数组
c1，c2：= 0，0
对于i，范围为0至n – 1

如果c1> c2，则将c1减1，否则将c2减1并res [i]：= 1
如果c1 <c2，则将c1加1，否则将c2加1并res [i]：= 1
如果seq [i] ='（'
除此以外

返回资源

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

示例

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("()(())()"))