Leetcode Valid Parentheses in Javascript

문제

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

접근

스택, 큐로 풀면 되는 문제지만 다른 방식으로 풀어보려고 interative하게 접근해보았다.

var isValid = function(s) {
    let map = new Map(); 
    map.set('{','}');
    map.set('(',')');
    map.set('[',']');
    
    const arr = s.split("");
    
    for(let i=0; i<arr.length; i++){
        const curr = arr[i];
        for(let j=i+1; j<arr.length; j++){
            if(arr[j] === map.get(curr)){
                arr.splice(arr.indexOf(curr));
                arr.splice(arr.indexOf(map.get(curr)));
            }
            console.log(arr);
        }
    }
    
    return arr.length > 0 ? false : true;
};

앞에선 나온 opening tag에 맞추어서 뒤에 나오는 closing tag를 삭제하는 방식으로 진행해보았는데

Input: s = "([)]"
Output: false

이 케이스를 true로 리턴하기 때문에 통과하지 못하였다. 그래서 그냥 스택을 이용해서 풀었다.

	/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let map = new Map(); 
    map.set('{','}');
    map.set('(',')');
    map.set('[',']');
    
    const arr = s.split("");
    const stack = [];
    
    for(let i=0; i<arr.length; i++){
        const curr = arr[i];
        if(map.has(curr)){
            stack.push(curr);
        }else{
            if(stack.length === 0 || map.get(stack.pop()) !== curr){
                return false;
            }
        }
    }
    
    return stack.length === 0;
};

괄호를 이용해 푸는 문제를 자주 접했는데, 괄호의 종류가 다양하다면 closing tag를 찾을 때

    let map = new Map(); 
    map.set('{','}');
    map.set('(',')');
    map.set('[',']');

Map을 통해서 찾는 방식이 유용해보인다.