LeetCode - 20. Valid Parentheses

Problem

(, ), [, ], {, }로만 이루어진 문자열 s가 주어질 때, s가 유효한지 아닌지 결정하라. 문자열은 아래의 조건에 맞을때 유효하다.

• 열린 괄호는 반드시 같은 종류의 괄호에 의해 닫혀야한다.
• 열린 괄호는 반드시 올바른 순서로 닫혀야한다.
• 닫힌 괄호는 같은 종류의 열린 괄호와 상응해야한다.

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

Solution

var isValid = function(s) {
    const stack = [];

    for(l of s) {
        if(l === '(' || l === '[' || l === '{') {
            stack.push(l);
        } else {
            if(l === ')' && stack[stack.length-1] === '('
            || l === ']' && stack[stack.length-1] === '['
            || l === '}' && stack[stack.length-1] === '{') {
                stack.pop();
            }
            else {
                return false;
            }
        }
    }

    return !stack.length;
};

Explanation

괄호가 열리면 반드시 닫혀야하고 먼저 열린 괄호일수록 나중에 닫혀야하기(선입후출) 때문에 스택을 이용해서 풀기로 했다.
for문을 이용해서 순회한다.
열린 괄호일 경우, 스택에 순서대로 추가한다.
닫힌 괄호일 경우, 스택의 맨 마지막에 있는 열린 괄호와 종류가 일치하면 제거한다. (괄호가 나중에 열릴수록 먼저 닫혀야 한다. 그래서 맨 마지막 괄호와 비교하는 것이다.)
여기서 일치하지 않으면 뒤에 있는 괄호는 확인할 필요가 없기 때문에 즉시 false를 리턴한다.
for문이 끝났을때 스택이 비어있으면 모든 괄호가 올바르게 열리고 닫혔다는 것이다.
따라서, 스택의 길이가 0일 경우 true이고 아닐 경우 false를 리턴한다.