【leetcode】1111. Maximum Nesting Depth of Two Valid Parentheses Strings

题目如下：

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 with B), where A and B are VPS's, or

It can be written as (A), where A 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)), where A and B are VPS's

depth("(" + A + ")") = 1 + depth(A), where A 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

解题思路：方法很简单，就是嵌套的括号进行均分，使得A = B或者A+1 = B 即可。用a_count和b_count分别记录A与B未配对的左括号数量。然后遍历seq，如果seq[i]为左括号，判断a_count与b_count的大小：如果a_count <= b_count ，表示这个左括号划分到A中，a_count ++；否则划分到B，b_count++。如果seq[i]是右括号，判断a_count与b_count的大小：如果a_count >= b_count ，表示这个右括号优先于A中的左括号匹配，a_count -- ；否则与B匹配，b_count --。

代码如下：

class Solution(object):

    def maxDepthAfterSplit(self, seq):

        """

        :type seq: str

        :rtype: List[int]

        """

        res = []

        a_count = 0

        b_count = 0

        a_s = ''

        b_s = ''

        for i in seq:

            if i == '(':

                if a_count <= b_count:

                    res.append(0)

                    a_count += 1

                    a_s += i

                else:

                    res.append(1)

                    b_count += 1

                    b_s += i

            elif i == ')':

                if a_count >= b_count:

                    res.append(0)

                    a_count -= 1

                    a_s += i

                else:

                    res.append(1)

                    b_count -= 1

                    b_s += i

        #print a_s,b_s

        return res

巴特西

【leetcode】1111. Maximum Nesting Depth of Two Valid Parentheses Strings

最新文章

热门文章