[LeetCode] Longest Valid Parentheses

문제

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

Example 1:

Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

 

Approach

우선 Valid parentheses의 조건을 잘 생각해봐야한다.

')'가 나왔을 때 그 바로 전에 '('가 있었다면 valid parentheses가 성립하고 [()]

')'가 나왔을 때 그 바로 전에 ')'가 있었다면 앞에 있던 ')'의 전전에 '('가 있어야 valid parentheses가 성립한다 [(())]

즉 초점을 '('가 아닌 ')'에 맞춰야 하고 이러한 점을 활용해 DP를 설계할 수 있다.

string의 i번째 글자까지 읽었을 때의 최대 valid parentheses의 길이를 memo[i]라고 한다면 (memo[i]는 0으로 초기화)

')'가 나왔을 때 그 바로 전에 '('가 있었다면 memo[i] = memo[i-1] + 2 가 된다.

그리고 ')'가 나왔을 때 그 바로 전에 ')'가 있었다면 memo[i] = memo[i-1] + memo[i - memo[i-1] - 2] + 2 가 된다.

이를 코드로 설계하면 O(n)만에 문제를 해결 할 수 있고, i-1과 i - memo[i-1] -2 가 0보다 작아지는 경우를 주의해야 한다.

 

Optimization

위 조건을 꼭 DP를 통해 해결해야 하는 것은 아니다.

스택을 통해서도 이를 똑같이 구현 할 수 있다.

-1을 담은 스택을 하나 만들고 string을 앞에서 부터 읽는다.

'('가 나오면 스택에 '('의 인덱스를 push하고

')'가 나오면 pop을 한다.

이 때 stack이 비면 ')'의 인덱스를 집어넣고 (처음에 -1로 시작한 것과 동일한 원리)

stack이 비지 않으면 현재 인덱스에서 top의 숫자를 뺀 숫자가 valid parentheses의 길이가 된다.

가장 긴 길이를 답으로 내면 된다.

이를 코드로 설계하면 O(n)만에 문제를 해결 할 수 있고 구현도 간단한다.

 

더 간단한 방법으로는

'('와 ')'의 숫자를 세면서 앞에서 부터 한번 읽고, 뒤에서 부터 한번 읽는 방법이 있다.

앞에서 부터 읽을 때 '('가 나오면 left를 1 더하고, ')'가 나오면 right를 1 더한다.

이 때 left == right가 되면 valid parentheses가 성립한다.

left < right가 되면 valid parentheses 조건이 깨지면서 left와 right를 0으로 초기화한다.

이를 뒤에서 부터 읽으면서 반복하여 가장 긴 길이를 답으로 낸다.

왜 되는지는 https://leetcode.com/problems/longest-valigd-parentheses/solution/ 에서..

 

Code

1. DP https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestValidParentheses_DP.cpp

chi3236/algorithm

2. Stack https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestValidParentheses_Stack.cpp

chi3236/algorithm

3. Two Pointers https://github.com/chi3236/algorithm/commit/4a56f3bb1b77f26afd5fd03deff03be165226725

LeetCode Longest Valid Parentheses · chi3236/algorithm@4a56f3b