[LeetCode] 32. Longest Valid Parentheses

https://leetcode.com/

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

Example 1:

nput: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

 

Example 2:

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

 

Example 3:

Input: s = ""
Output: 0

 

Constraints:

• 0 <= s.length <= 3 * 10^4
• s[i] is '(', or ')'.

Code :

function longestValidParentheses(s) {
    const stack = []; // 스택 초기화
    let maxLen = 0; // 최대 길이 초기화
    let start = -1; // 시작 인덱스 초기화

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') { // 여는 괄호인 경우 스택에 인덱스를 추가
            stack.push(i);
        } else { // 닫는 괄호인 경우
            if (stack.length === 0) { // 스택이 비어있는 경우 시작 인덱스를 업데이트
                start = i;
            } else { // 스택이 비어있지 않은 경우
                stack.pop(); // 스택에서 가장 최근에 추가된 여는 괄호 인덱스 제거
                if (stack.length === 0) { // 스택이 비어있는 경우
                    maxLen = Math.max(maxLen, i - start); // 최대 길이 업데이트
                } else { // 스택이 비어있지 않은 경우
                    maxLen = Math.max(maxLen, i - stack[stack.length - 1]); // 최대 길이 업데이트
                }
            }
        }
    }

    return maxLen; // 최대 길이 반환
};

 

Solutions Code :

var longestValidParentheses = function(S) {
    let stack = [-1]; // 스택 초기화, 초기 인덱스를 -1로 설정
    let ans = 0; // 결과값 초기화

    for (let i = 0; i < S.length; i++) {
        if (S[i] === '(') { // 여는 괄호인 경우 스택에 인덱스 추가
            stack.push(i);
        } else if (stack.length === 1) { // 스택의 길이가 1인 경우
            stack[0] = i; // 스택의 첫 번째 원소를 현재 인덱스로 업데이트
        } else { // 스택이 비어있지 않은 경우
            stack.pop(); // 스택의 가장 최근에 추가된 원소를 제거
            ans = Math.max(ans, i - stack[stack.length-1]); // 최대 길이 업데이트
        }
    }
    return ans; // 최대 길이 반환
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode