[leetcode][TS] 20. 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.

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

 

예시

코드

function isValid(s: string): boolean {
    const stack:Array<string> = [];
    
    const matchBrackets:{[key:string]:string} = {
        ')' : '(',
        ']' : '[',
        '}' : '{'   
    };
    
    
    for(const bracket of s){
        if(bracket in matchBrackets){ // 닫힌 괄호
            if(stack.length === 0) return false;
            if(stack.pop() !== matchBrackets[bracket]) return false;
        }
        else{ // 열린 괄호
            stack.push(bracket);
        }
    }
    
    // 열린 괄호만 남아있을 수도 있음
    return stack.length === 0;
    
    
};

 

괄호가 올바르게 짝이 맞는지 확인하는 문제이다. 열린 괄호일 때는 스택에 추가하고, 닫힌 괄호일 때는 스택에 가장 상단에 있는 괄호를 뽑아서 닫힌 괄호와 짝이 맞는 열린 괄호인지 확인한다. 만약 짝이 맞지 않는다면 올바른 괄호가 아니기 때문에 `false`를 리턴해준다. 물론, 그 전에 스택이 비어 있다면 앞에 있던 열린 괄호가 다 뽑혔다는 의미이므로, 스택이 비어있을 때 바로 `false`를 리턴한다. 또한, 열린 괄호가 닫힌 괄호보다 많이 존재했다면 올바른 괄호가 될 수 없기 때문에 마짐가에 스택이 비어있지 않으면 `false`를 리턴하도록 한다.