Вирішуємо завдання «Valid Parentheses»

Умова

Дано рядок, який складається з круглих, фігурних, квадратних дужок. Визначити чи є рядок правильним. Рядок правильний, якщо:

1) Відкрита дужка закрита дужкою такого ж типу.

2) Всі дужки закриті у правильному порядку.

Обмеження:

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

2) У рядку зустрічаються лише такі дужки: '()[]{}'.

Given a string s налаштованими just 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 в the correct order.

приклад

a)
Input: s = "()[]{}"
Output: true
b)
Input: s = "([)]"
Output: false
c)
Input: s = "{[]}"
Output: true

Рішення

Основна складність цього завдання полягає в тому, що дужки можуть відкриватися та закриватися як одразу (приклад a), так і з часом (приклад b). Ключ до розв'язання полягає в тому, що у валідному рядку при переборі його символів зліва направо, перша зустрічна закриваюча дужка повинна відразу ж закривати відкриваючу дужку свого типу. Якщо при цьому ми виключатимемо таку пару валідних дужок з рядка, то наступна закриваюча дужка, за таким же принципом повинна закривати відкриту дужку свого типу. На прикладі c видно, що перша закриваюча дужка — фігурна, і вона відразу ж закриває відкриваючу фігурну — це валідна пара. Якщо ми виключимо цю пару з рядка і подивимося на те, що залишилося, побачимо, що наступна закриваюча дужка — квадратна, і вона також закриває відкриваючу квадратну. Якщо виключимо цю пару з рядка, отримаємо в результаті порожній рядок, це ще одна відмінна риса валідного рядка. А тепер докладніше про реалізацію.

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

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

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];

            // Checking whether the current bracket is a closing bracket
            if (mapping.hasOwnProperty(character)) {
                if (stack.length === 0) {
                    /*
                    * The current bracket is a closing bracket, but the stack is empty, so
                    * this bracket has nothing to close, and the string is invalid
                    * */
                    return false;
                }

                const topElement = stack[stack.length - 1];
                /*
                * Check if the type of the current closing bracket matches
                * the type of the last bracket in the stack
                * */
                if (topElement === mapping[character]) {
                    stack.pop();
                } else {
                    /*
                    * the type doesn't match, so the closing parenthesis is not appropriate,
                    * which means the string is invalid
                    * */
                    return false;
                }
            } else {
                // The current bracket is an opening bracket, add it to the stack
                stack.push(character);
            }
        }

        // if the stack is empty, the string is valid
        return stack.length === 0;
    };