Решаем задачку «Valid Parentheses»

Условие

Дана строка, которая состоит из круглых, фигурных, квадратных скобок. Определить является ли строка правильной. Строка правильная, если:

1) Открытая скобка закрыта скобкой такого же типа.

2) Все скобки закрыты в верном порядке.

Ограничения:

1) 1 <= s.length <= 10⁴

2) В строке встречаются только следующие скобки: ‘()[]{}’.

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.

Пример

а)
Input: s = "()[]{}"
Output: true
б)
Input: s = "([)]"
Output: false
в)
Input: s = "{[]}"
Output: true

Решение

Основная сложность этой задачи заключается в том, что скобки могут открываться и закрываться как сразу (пример а), так и со временем (пример б). Ключ к решению состоит в том, что в валидной строке при переборе ее символов слева направо, первая, встретившаяся нам, закрывающая скобка должна сразу же закрывать открывающую скобку своего типа. Если при этом мы будем исключать такую пару валидных скобок из строки, то следующая закрывающая скобка по такому же принципу должна закрывать открытую скобку своего типа. На примере в видно, что первая закрывающая скобка — фигурная, и она сразу же закрывает открывающую фигурную — это валидная пара. Если мы исключим эту пару из строки и посмотрим на то, что осталось, увидим, что следущая закрывающая скобка — квадратная, и она также закрывает открывающую квадратную. Если исключим и эту пару из строки, получим в итоге пустую строку, это еще одна отличительная черта валидной строки. А теперь подробнее о реализации.

Для перебора строки можно использовать цикл, а для аккумулирования скобок, с возможностью легко достать крайнюю, лучше всего подходит стэк. В таком случае, при переборе строки мы будем складывать каждую открывающую скобку в стэк, а когда встретим закрывающую, проверим скобку из верхушки стэка на тип и если он совпадает, удалим ее из стека. В конце посмотрим на размер стека, если он будет равен нулю, значит количество открывающих и закрывающих скобок разного типа совпало и строка валидная. Визуально это будет выглядеть так:

Для маппинга типа скобок можно использовать такую конструкцию:

const mapping = {
        ')': '(',
        '}': '{',
        ']': '[',
    };
Object.freeze(mapping);

Константа не даст нам случайно присвоить новое значение, а Object.freeze подмешать в нее новые свойства. Код целиком:

    const mapping = {
        ')': '(',
        '}': '{',
        ']': '[',
    };

    var isValid = function(s) {
        Object.freeze(mapping);
        const stack = [];

        for (let i = 0; i < s.length; i++) {
            const character = s[i];

            // Проверка на то, является ли текущая скобка закрывающей
            if (mapping.hasOwnProperty(character)) {
                if (stack.length === 0) {
                    /*
                    * Текущая скобка закрывающая, а стек пустой, значит закрывать этой скобке
                    * нечего, а строка невалидная
                    * */
                    return false;
                }

                const topElement = stack[stack.length - 1];
                /*
                * Проверка на то, совпадает ли тип текущей закрывающей скобки
                *  с типом крайней скобки из стэка
                * */
                if (topElement === mapping[character]) {
                    stack.pop();
                } else {
                    /*
                    * тип не совпадает, тут закрывающая скобка не к месту,
                    * а значит, строка невалидная
                    * */
                    return false;
                }
            } else {
                // Текущая скобка открывающая, добавляем ее в стэк
                stack.push(character);
            }
        }

        // если стэк пустой, то строка валидная
        return stack.length === 0;
    };