[LeetCode-JS] Valid Parentheses

🙋 문제: 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.
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 '()[]{}'.

🅰️ 풀이:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s.length % 2 !== 0 ) {return false} //문자열이 짝수여야 성립되므로. 홀수인 경우 false
    const hash = {"(": 1, ")": -1, "[": 2, "]": -2, "{": 3, "}": -3}
    if(hash[s[0]] < 0) {return false} // 첫 번째 글자는 무조건 여는 괄호, 양수여야 성립.
    let plus = [hash[s[0]]];
    for(let i = 1; i < s.length; i++){
        if (hash[s[i]] < 0 && Math.abs(hash[s[i]]) === plus[plus.length -1]){
            plus.pop(hash[s[i-1]])
        } else if(hash[s[i]] > 0){
            plus.push(hash[s[i]])
        } else{
            plus.unshift(hash[s[i]])
        }
    }
    if (plus.length === 0){
        return true
    }
    return false
};

>>  "해쉬테이블을 사용해야지"하고 시작해서... 조건을 계속 추가하게 되었다.. 시간이 꽤 걸렸지만 풀긴 풀었돠....

let plus~ 부터 설명해보면, 앞선 조건들에 의해 문자열의 첫 번째는 여는 괄호일 테니 plus 배열에 넣어준다.

다음 문자(기호)부터 for문을 이용해서, 음수(닫는 기호)이면서 절대값이 plus 배열의 마지막 값과 일치하면 배열에서 pop, 제거하고,

else if 양수(여는 기호)가 나오면 plus 배열에 push, 추가하고,

else 위의 조건들이 아닌 경우, plus 배열에 unshift, 배열 앞쪽으로 추가한다. 

그다음에, plus 배열에 값이 0이면, 제대로 열고 닫힌 경우로, true가 된다. 

 

>> 이걸 작성하는 현재, 다른 풀이는 아직 보지 못했는데... 복잡하게 푼 건가 싶다. 아무튼 I made it.

 

✅ 다른 사람 풀이:

var isValid = function(s) {
    const stack = [];
    const map = {
        '(': ')',
        '{': '}',
        '[': ']',
    }

    for(let i = 0; i < s.length; i++) {
        if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
            stack.push(s[i]);
        } else if (map[stack.pop()] !== s[i]) {
            return false;
        }
    }
    
    return !stack.length;
};

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

>> 해쉬테이블에서 괄호들을 숫자로 할 게 아니라, '열린 괄호 :  닫힌 괄호'로 매칭해주면 간단했던 것이었다!!!

>> 여는 괄호는 stack에 담고, 여는 괄호가 아닌 (닫는 괄호라면) stack에서 팝하는데, 그게 해쉬테이블에 매치되지 않으면, false. 

>> 마지막줄, return !stack.length 는 true가 나오는데, return true로 해도 되려나 싶었는데 "(", "(("와 같이 여는 괄호만 있을 때는 true가 나와서 Wrong answer!!이 되었다.

var isValid = function(s) {
    let arr = [];
    if(s.length%2 !== 0)return false;
    for(let i=0; i< s.length; i++){
        if(s[i] === ')' || s[i] === ']' || s[i] === '}'){
            if(arr.length== 0)return false
            el = arr.pop()
            if(s[i] === ')' && (el === '{' || el === '['))return false;
            if(s[i] === '}' && (el === '(' || el === '['))return false;
            if(s[i] === ']' && (el === '{' || el === '('))return false;
        }else{
            arr.push(s[i])
        }
    }
    return arr.length === 0;
};

var isValid = function(s) {
     let stack = [];
    
    for (let i = 0 ; i < s.length ; i++) {
        let c = s.charAt(i);
        switch(c) {
            case '(': stack.push(')');
                break;
            case '[': stack.push(']');
                break;
            case '{': stack.push('}');
                break;
            default:
                if (c !== stack.pop()) {
                    return false;
                }
        }
    }
    
    return stack.length === 0;
    
};

>> charAt() 함수는 문자열에서 특정 인덱스에 위치하는 유니코드 단일문자를 반환합니다. index를 제공하지 않으면 기본값은 0입니다.