LeetCode 1614 solution

problem

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

• It is an empty string "", or a single character not equal to "(" 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(C) = 0, where C is a string with a single character not equal to "(" or ")".
• 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 represented as string s, return the nesting depth of s.

Example 1:

• Input: s = "(1+(2*3)+((8)/4))+1"
• Output: 3
• Explanation: Digit 8 is inside of 3 nested parentheses in the string.

python

class Solution:
    def maxDepth(self, s: str) -> int:
        stack, res = [], 0
        for i in s:
            if i == "(":
                stack.append(i)
                res = max(res, len(stack))
            elif i == ")":
                stack.pop()
        return res

아주 기본적이면서도 간단한 stack 문제이다. 잘 막힌 괄호에 대한 문제는 굉장히 많다. 이 문제는 기본적으로 VPS라고 해서 괄호가 잘 막혀 있는 string 파라미터로 전달해준다. 이에 대해서 depth 판별하는 문제이다.

stack에 (일 경우에는 쌓아주면서 동시에 결과 int를 max로 계속해서 갱신해준다. )를 만나는 경우에는 pop으로 stack에서 ()로 닫힌 경우에 대한 제거를 해준다.