Решаем задачку «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.

Пример

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