32. Longest Valid Parentheses

무지성 포칼포인트의 답...

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        
        mem = [0] * len(s)
        stack = []
        length = 0
        for i in range(len(s)):
            char = s[i]
            if char == '(':
                stack.append(char)
                length = 0
            else:
                if not stack:
                    length = 0
                else:
                    top = stack.pop()
                    if top == '(':
                        length += 2
                        if i - length >= 0 and s[i-length] == ')':
                            length += mem[i-length]
                    else:
                        length = 0
            mem[i] = length
        return max(mem)

 

괴수의 답...

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        dp = [0] * (len(s) + 1)     
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                if stack:
                    corresponding_idx = stack.pop()
                    dp[i+1] = dp[corresponding_idx] + i - corresponding_idx + 1
        return max(dp)