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

2023-11-16 08:32:34

假设我们有一个字符串,当且仅当该字符串仅由“(”和“)”字符组成且满足这些属性时,该字符串才是有效的括号字符串(表示为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("()(())()"))

    输入值

    "()(())()"

    输出结果

    [1, 1, 1, 0, 1, 0, 1, 1]
    • 作者:
    • 原文链接:
      更新时间:2023-11-16 08:32:34