문자열이 있다고 가정하고 해당 문자열은 "(" 및 ")" 문자로만 구성되고 이러한 속성을 충족하는 경우에만 유효한 괄호 문자열(VPS로 표시)입니다 -
-
빈 문자열이거나
-
AB로 쓸 수 있습니다. 여기서 A와 B는 VPS 또는
-
(A)로 쓸 수 있습니다. 여기서 A는 VPS입니다.
우리는 또한 아래와 같이 모든 VPS S의 중첩 깊이 깊이(S)를 정의할 수 있습니다 -
-
깊이("") =0
-
깊이(A + B) =깊이(A)의 최대값, 깊이(B), 여기서 A와 B는 VPS
-
depth("(" + A + ")") =1 + depth(A), 여기서 A는 VPS입니다.
VPS seq가 있는 경우 A와 B가 VPS(및 A의 길이 + B의 길이 =seq의 길이)가 되도록 두 개의 분리된 하위 시퀀스 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 :=길이가 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]