Pythonでの2つの有効な括弧文字列の最大ネスト深度

文字列があり、その文字列が「（」および「）」文字のみで構成され、これらのプロパティを満たしている場合にのみ、有効な括弧文字列（VPSで示される）であるとします-

• 空の文字列、または

• ABと書くことができます。ここで、AとBはVPS、または

• （A）と書くことができます。ここで、AはVPSです。

以下のように、任意のVPS Sのネスト深度の深さ（S）を定義することもできます-

• 深さ（ ""）=0

• 深さ（A + B）=深さ（A）、深さ（B）の最大値。ここで、AとBはVPSです

• 深さ（ "（" + A + "）"）=1 +深さ（A）、ここでAはVPSです。

VPSシーケンスがある場合、AとBがVPSになるように（そしてAの長さ+Bの長さ=シーケンスの長さ）、2つの互いに素なサブシーケンスAとBに分割する必要があります。ここで、max（depth（A）、depth（B））が可能な最小値になるようなAおよびBを選択した場合。次に、AとBのそのような選択をエンコードする（seqの長さの）回答配列を見つける必要があります。seq[i]がAの一部である場合はanswer [i] =0、それ以外の場合はanswer [i]=1です。

したがって、入力が「（）（（））（）」の場合、出力は[1,1,1,0,1,0,1,1]

これを解決するには、次の手順に従います-

• n：=seqの長さ、res：=0の長さがnである0の配列

• c1、c2：=0、0

• 0からn–1の範囲のiの場合

  • seq [i] =‘（’

    • c1

  • それ以外の場合

    • c1> c2の場合、c1を1減らし、そうでない場合はc2を1減らし、res [i]：=1

• 解像度を返す

理解を深めるために、次の実装を見てみましょう-

例

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]