動機
題目寫得很爛,但題目本身很有趣!!
題目想做的事是把string的括號分成兩組,讓兩組的深度越小越好 回傳每個括號是分配到哪一組
Problem
A string is a valid parentheses string (denoted VPS) if and only if it consists of "("
and ")"
characters only, and:
- It is the empty string, or
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are VPS's, or - It can be written as
(A)
, whereA
is a VPS.
We can similarly define the nesting depth depth(S)
of any VPS S
as follows:
depth("") = 0
depth(A + B) = max(depth(A), depth(B))
, whereA
andB
are VPS'sdepth("(" + A + ")") = 1 + depth(A)
, whereA
is a VPS.
For example, ""
, "()()"
, and "()(()())"
are VPS's (with nesting depths 0, 1, and 2), and ")("
and "(()"
are not VPS's.
Given a VPS seq, split it into two disjoint subsequences A
and B
, such that A
and B
are VPS's (and A.length + B.length = seq.length
).
Now choose any such A
and B
such that max(depth(A), depth(B))
is the minimum possible value.
Return an answer
array (of length seq.length
) that encodes such a choice of A
and B
: answer[i] = 0
if seq[i]
is part of A
, else answer[i] = 1
. Note that even though multiple answers may exist, you may return any of them.
Example 1:
Input: seq = "(()())"Output: [0,1,1,1,1,0]
Example 2:
Input: seq = "()(())()"Output: [0,0,0,1,1,0,1,1]
Constraints:
1 <= seq.size <= 10000
Sol
就是把括號分成兩半,依據深度!!
class Solution:
def maxDepthAfterSplit(self, seq: str) -> List[int]:
ret = []
d = 0
for c in seq:
left = (c == "(")
if left:
d += 1
ret += int(d % 2 == 0),
if not left:
d -= 1
return ret