Valid Parentheses

Условие

Дана строка, состоящая из символов '(', ')', '{', '}', '[', ']'. Необходимо определить, является ли строка корректной последовательностью скобок. Строка считается корректной, если:

1. Открытые скобки закрываются скобками того же типа.

2. Открытые скобки закрываются в правильном порядке.

Примеры

Input: s = "()”

Output: true

Input: s = "()[]{}”

Output: true

Input: s = "(]”

Output: false

Input: s = "([])”

Output: true

Решение

fun isValid(s: String): Boolean {
    // Стек для хранения открывающих скобок
    val stack = mutableListOf<Char>()

    // Карта соответствия закрывающих и открывающих скобок
    val matchingParentheses = mapOf(
        ')' to '(', // Круглые скобки
        '}' to '{', // Фигурные скобки
        ']' to '['  // Квадратные скобки
    )

    // Проходим по каждому символу строки
    for (char in s) {
        // Если символ - закрывающая скобка
        if (char in matchingParentheses.keys) {
            // Извлекаем последний элемент из стека или присваиваем "пустой символ", если стек пуст
            val topElement = if (stack.isNotEmpty()) stack.removeAt(stack.size - 1) else '#'

            // Проверяем, соответствует ли закрывающая скобка последней открывающей
            if (topElement != matchingParentheses[char]) {
                return false // Если не соответствует, строка невалидна
            }
        } else {
            // Если символ - открывающая скобка, добавляем его в стек
            stack.add(char)
        }
    }

    // Если после обхода строки стек пуст, значит все скобки закрыты корректно
    return stack.isEmpty()
}

Временная сложность

O(n), где n — длина строки. Мы проходим по каждому символу строки ровно один раз, выполняя операции добавления и удаления элементов из стека.

Пространственная сложность

O(n), где n — длина строки. В худшем случае все символы могут быть открывающими скобками, и они будут помещены в стек.