20. Valid Parentheses

Задача

Дана строка из скобок ()[]{}. Определите, корректно ли расставлены скобки (каждая закрывается той же и в правильном порядке).

Решение

Решение

// Временная сложность: O(n)
// Пространственная сложность: O(n)
 
function isValidBrackets(str) {
    const stack = [];
 
    const brackets = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
 
    const opening = new Set(['(', '[', '{']);
 
    for (let char of str) {
        if (opening.has(char)) {
            stack.push(char);
        } else if (char in brackets) {
            if (stack.length === 0 || stack.pop() !== brackets[char]) {
                return false;
            }
        }
        // Остальные символы игнорируем
    }
 
    return stack.length === 0;
}

Решение 2 (компактнее)

// Временная сложность: O(n)
// Пространственная сложность: O(n)
 
function isValidBrackets(str) {
    const stack = [];
    const pairs = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
 
    // Создаем Set-ы для мгновенного поиска O(1)
    const opening = new Set(['(', '[', '{']);
    const closing = new Set([')', ']', '}']);
 
    for (const char of str) {
        if (opening.has(char)) {
            stack.push(char);
        } else if (closing.has(char)) {
            if (stack.pop() !== pairs[char]) return false;
        }
    }
 
    return stack.length === 0;
}

Решение 3 (Deque)

var isValid = function(s) {
    const deque = [];
 
    for (let char of s) {
        if (char === '(') deque.push(')');
        else if (char === '{') deque.push('}');
        else if (char === '[') deque.push(']');
        else if (deque.length === 0 || deque.pop() !== char) {
            return false;
        }
    }
 
    return deque.length === 0;
};