스터디 3주차 / leetcode 20번 / Valid parentheses / JavaScript

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

문제에서 제공하는 예제 입력이 사실 좀 친절하지 않아서,, 문제의 조건들만 봤을때는 헷갈린 부분이 있어서 discussion탭에 들어가서 확인 해봤습니다. 제가 생각했던 것처럼 { [ ( ) ] } 같은 test case도 true를 반환할 수 있게끔 만들어야 하는 문제 였습니다. 아래는 코드 설명입니다.

 

비어있는 stack 배열을 하나 만들고 , 입력으로 들어오는 s를 순회하면서 open bracket일 때 close bracket을 스택에 차곡차곡 넣어줍니다. open bracket보다 clsoe bracket이 먼저 들어오면 문제의 조건을 만족시키지 못하기 때문에 곧장 return false를 만나게 되어있습니다. 그렇게 스택에 차곡차곡 쌓다가 , s에서 닫는 브라켓이 나오는 순간 스택에서 pop하여 가장 최근 넣었던 오픈 브라켓과 같은 모양의 닫는 브라켓을 꺼내어 비교해보고 같으면 통과 , 다르면 false를 리턴하여 함수를 종료합니다. 또한 마지막으로는 ' [ [ ' 과 같은 경우를 대비하여 stack에 넣기만 하고 빼지 못한 경우엔 당연히 조건을 충족시키지 못해 false를 리턴하게끔 합니다.

 

 

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    
    for (let i = 0; i<s.length; i++)
    {
        if (s[i] === '(')
        {
            stack.push(')');
        }
 
        else if (s[i] === '[')
        {
            stack.push(']');
        }
 
        else if (s[i] === '{')
        {
            stack.push('}');
        }
 
        else if (stack.pop() !== s[i])
        {
            return false;
        }
 
    }
 
    if (stack.length > 0)
    {
        return false;
    }
 
    return true;
};