[leetcode 32] Longest Valid Parentheses

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

가장 긴 well formed parentheses 찾기

 

Example 1:

Input: 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

 

풀이:

- 난이도가 hard라 어렵당..

- 스택으로 풀기:맨 첨에 -1을 push

'('는 인덱스를 push, ')'는 일단 pop을 한다. (이전에 저장된 값이 '('이거나 ')'일 수 있다.)

pop이후에

여태 문자열이 well formed였다면 -1만 남는 상태(not empty) ->첫 시작이 -1로 계속 최대 길이가 업데이트

중간에 well formed가 파괴되면 -> -1도 pop되고 스택이 empty상태가 됨. empty일때마다 현재 위치를 푸쉬해서 다음 '()'이 나올때까지 반복

class Solution {
public:
    int longestValidParentheses(string s) {
        int result = 0;
        stack<int> stk;
        stk.push(-1);
        
        for(int i=0; i<s.length(); i++){
           
            if(s[i]=='('){
                stk.push(i);
            }else {
               stk.pop();
                if(!stk.empty()){
                    int top = stk.top();
                    result = max(i-top, result);
                }else {
                    stk.push(i);
                }
            }
        }
        return result;
    }
};

 

재밌는 풀이 추가

1) 왼쪽에서부터 순회

- (가 등장하면 left++, )가 등장하면 right++

- left=right라면 올바른 문자열이므로 max를 업데이트

- right가 더 커지면 올바른 문자열이 깨진다는 의미: left = right = 0으로 설정한다.

- 하지만 왼쪽에서부터 순회하면 ((()의 경우 즉, '('가 많아서 left=right조건을 만족시키지 못하는 경우가 발생한다.

따라서 맨 오른쪽에서부터 순회하는 것도 필요하다. 오른쪽에서부터 순회하면 ())))에서 업데이트가 안됨 

- 어찌됐든 둘다 해줘야 최대 길이 찾는게 가능하다.

 

class Solution {
public:
    int longestValidParentheses(string s) {
        
        int left = 0, right = 0, maxLen = 0;
        for(int i=0; i<s.length(); i++){
            if(s[i]=='('){
                left++;
            }else{
                right++;
                
                if(left==right){
                        maxLen = max(maxLen, right*2);
                }else if(right>left){
                        left=right=0;
                }
            }
        }
        
        left = 0, right = 0;
        for(int i=s.length()-1; i>-1; i--){
            if(s[i]=='('){
                left++;
                if(left==right){
                    maxLen = max(maxLen, left*2);
                }else if(left>right){
                    left=right=0;
                }
                
            }else{
                right++;
            }
        }
    return maxLen;
    }

};