[leetcode] Valid Parentheses

victor·2021년 1월 21일
0

알고리즘

목록 보기
17/63

Problem

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Example 5:

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

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

code

// Time complexity: O(N)
// Space complexity: O(N) when input is like "(((((("

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

    for (let c of s)
        if (c == '(' || c== '{' || c == '[') arr.push(c);
        else 
            if (arr.length == 0 || map[arr.pop()] != c) 
                return false;
    
    return arr.length == 0; 
};
profile
캬-!

0개의 댓글