[LeetCode] Valid Parentheses

문제

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.

풀이

error 발생

var isValid = function(s) {
    let stack = [];
    const left = ['(','{','['];
    for (var i=0;i<s.length;i++){
        if (left.includes(s[i])) {
            stack.push(s[i]);
        } else {
            if (stack[stack.length-1]==='(' && s[i]===')'){
                stack.pop();
            } else if (stack[stack.length-1]==='[' && s[i]===']'){
                stack.pop();
            } else if (stack[stack.length-1]==='{' && s[i]==='}'){
                stack.pop();
            }
        }
    }
    if (stack.length>0) {
        return false
    } else {
        return true
    }
};

• stack에 왼쪽괄호가 들어오면 push하고 오른쪽 괄호가 들어오면 stack의 제일 상단에 있는 괄호와 비교하여 짝이 맞으면 pop하는 로직을 구현하였다.
• 모든 문자를 돌고 만약에 stack의 길이가 0이면 올바른 문자열이기 때문에 true를 반환하고 아니라면 짝이 안맞기 때문에 false를 반환하게 하였다.
• 하지만 "]" 문자가 들어오면 오류가 발생했다. 해당 문자는 오른쪽 괄호 하나만 있기 때문에 처음부터 stack배열에 들어가지 않아서 올바른 문자열이 아니지만 true 값을 반환하기 때문이다.

해결 코드

var isValid = function(s) {
    const paris = {'(':')','{':'}','[':']'};
    let stack = [];
    for (var i=0;i<s.length;i++) {
        if (s[i] in paris) {
            stack.push(s[i]);
        } else {
            let close = stack.pop();
            if (paris[close]!==s[i]){
                return false
            }
        }
    }
    return stack.length === 0
};

• map을 활용하여 왼쪽괄호가 들어오면 오른쪽 괄호를 넣어준다. 오른쪽 괄호가 들어온다면 stack의 제일 상단에 있는 괄호와 비교하여 다르다면 올바르지 않은 문자이기 때문에 false를 반환한다.
• 마지막에 길이를 통해 true,false를 구분하여 최종값을 return한다.