[Leetcode] 32. Longest Valid Parentheses

문제 : https://leetcode.com/problems/longest-valid-parentheses/

---

'(', ')' 문자만 포함한 문자열이 주어질 때, 가장 긴 유효한 괄호 부분 문자열의 길이를 구하여라.

---

DP + Stack

dp[i] = s[~i] 문자열에서 s[i]를 포함한 부분 문자열의 가장 긴 유효한 괄호 부분 문자열 길이.

stack 열린 괄호 문자 인덱스

문자열 s를 앞에서부터 탐색하면서 열린 괄호 문자면 스택에 저장하고 닫힌 괄호 문자이면서 스택에 값이 있으면 top 값을 가져온다.

 

top은 현재 탐색 중인 닫힌 괄호 문자와 매칭 되는 열린 괄호 문자의 인덱스(let, index)이며 

dp[i] = (i - index + 1) + dp[index-1]

dp의 점화식은 위와 같다. 

 

 

시간, 공간복잡도는 O(|s|)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/32.%20Longest%20Valid%20Parentheses.cpp