[Leetcode]32. Longest Valid Parentheses

Problem

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

example
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Solution

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res=0
        cur=0 #most important variable
        stk=[]
        
        for c in s:
            if c=="(":
                stk.append(cur) 
                cur=0
            elif c==")":
                if stk:
                    cur=stk.pop()+cur+1 #important
                    if cur>res:
                        res=cur
                else:#don't forget to initialize cur unable to make a  pair.
                    cur=0
        
        return res*2

이 풀이에서 가장 중요한 개념은 variable cur이다.
우선 open parenthese의 개수를 level로 생각하였다. (()())에서 맨 바깥 소괄호는 같은 level이고, 안에 있는 ()()가 같은 level이 되는 것이다.

이 때 cur의 의미는 같은 레벨에서 이미 만들어진 parentheses pair 갯수이다.
따라서 각 문자를 iterate할 때 cur은 다음과 같다.

<iteration 과정>

(()()) - 같은 레벨에서는 이미 만들어진 괄호쌍이 없다. 따라서 cur=0이 스택에 쌓인다.
(()()) - 마찬가지로 같은 레벨에서는 괄호쌍이 없다. 바로 앞의 괄호는 다른 레벨이다. 따라서 스택에 0이 하나더 쌓인다.
(()()) - cur=stk.pop()+cur+1 연산이 실행된다. 이 때 stk.pop()은 이전에 같은 레벨에서 만들어진 괄호쌍을 의미하고 cur은 지금 닫고 있는 괄호 안에 있는 괄호 쌍을 의미한다.(한 단계 아래 레벨에서 만들 수 있는 괄호 쌍) 그리고 1은 자기 자신이다.
(()()) - 같은 레벨에서 괄호 쌍이 하나 만들어졌기 때문에 cur이 1이다. 따라서 stack에 1이 쌓인다.
(()()) - 이 때 stk.pop()이 1이고, cur은 0이므로, 최종적으로 cur=stk.pop()+cur+1=2가 된다.
(()()) - stk.pop()은 0이고(첫번째 줄에서 넣은 0) cur은 2가 되므로 최종적으로 cur은 3이 된다.

처음에는 cur=stk.pop()+1이라고 했다가 테스트 케이스에서 걸러졌다. 또한 close parenthese 갯수가 더 많은 경우, 유효한 괄호 쌍으로 확장할 수 없는 경우임으로 cur을 0으로 초기화하는 것도 잊지 않아야 한다.