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