32. Longest Valid Parentheses (String, Dynamic Programming, Stack)

링크 - https://leetcode.com/problems/longest-valid-parentheses/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

1) Stack

우리는 stack을 이용해 문제를 풀 수 있다. 먼저 stack에 -1을 넣어줘야하는게 포인트이다. 그 다음 (가 나오면 stack에 현재 index를 append하고, )가 나오면 stack을 pop한다. 그리고 현재 stack이 있으면 i - stack[-1]을 통해 ans을 업데이트하고, stack이 비어있으면 현재 index를 stack에 append한다.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        ans = 0
        stack = []
        stack.append(-1)

        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    ans = max(ans, i - stack[-1])

        return ans

Time Complexity: O(n) s를 for문으로 돌기 때문이다.

Space Complexity: O(n) stack의 크기는 n까지 증가할 수 있다.

2) No extra space

우리는 stack없이도 이 문제를 풀 수있다. 이를 위해서는 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 2번의 스캔이 필요하다. 왼쪽에서 오른쪽으로 갈때는 )개수가 더 많아지면 거기서부터 이미 invalid하므로, num_opens와 num_closes를 0으로 초기화 한다. 반대로 오른쪽에서 왼쪽으로 갈때는 (개수가 더 많아지면 거기서부터 이미 invalid하므로, num_opens와 num_closes를 0으로 초기화 한다.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        num_opens, num_closes, ans = 0, 0, 0

        for i in range(len(s)):
            if s[i] == "(":
                num_opens += 1
            else:
                num_closes += 1

            if num_opens == num_closes:
                ans = max(ans, 2 * num_closes)
            elif num_closes > num_opens:
                num_opens = num_closes = 0

        num_opens = num_closes = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == "(":
                num_opens += 1
            else:
                num_closes += 1

            if num_opens == num_closes:
                ans = max(ans, 2 * num_closes)
            elif num_opens > num_closes:
                num_opens = num_closes = 0

        return ans

 

Time Complexity: O(n) s를 for문으로 2번 돌기 때문이다.

Space Complexity: O(1)