[알고리즘] LeetCode - 32. Longest Valid Parentheses

Description

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 "()()"

풀이

Brute force로 풀면 시간 복잡도가 O(n^3) 이므로 좀 더 효율적인 방법을 찾아보자.

1. Stack 활용하기

1. 먼저 stack에 초기값으로 -1을 넣어준다.
2. Input string을 순회하면서 "("을 만나면 stack에 해당 index를 넣어준다.
3. ")"인 경우 stack의 element 하나를 제거한다. 그 다음:
   1. stack에 element가 없는 경우: 현재 index를 stack에 넣어준다.
   2. stack에 element가 있는 경우: 현재 index와 stack의 top element의 차이가 현재 valid substring의 길이가 되므로 maxLength와 비교하여 값을 설정해준다.
4. 순회가 종료된 후 maxLength를 반환한다.

2. DP

는 나중에...

구현코드

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  const stack = [-1];
  let maxLength = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(i);
    } else if (s[i] === ")") {
      stack.pop();
      if (stack.length) {
        const length = i - stack[stack.length - 1];
        maxLength = Math.max(maxLength, length);
      } else {
        stack.push(i);
      }
    }
  }
  return maxLength;
};

Complexity?

Stack을 한차례 순회하면 끝이므로 O(n)의 시간복잡도로 문제를 해결할 수 있다.
Input string외에 n과 비례하는 공간을 차지하는 stack을 필요로 하므로 O(n)의 공간복잡도를 가진다.