Premium

Стеки

Корректные скобки

Проверить корректность скобочной последовательности

Легкий

Постановка задачи

Описание (LeetCode - 20. Valid Parentheses)

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

Строка корректна, если:

  1. Каждая открывающая скобка закрывается скобкой того же типа.
  2. Скобки закрываются в правильном порядке.
  3. Каждая закрывающая скобка имеет соответствующую открывающую.

Пример 1:

s = "()"

Результат:

true

Пример 2:

s = "()[]{}"

Результат:

true

Пример 3:

s = "(]"

Результат:

false

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

  • 1 <= s.length <= 10⁴
  • s состоит только из символов ()[]{}

Решение

Эта задача идеально подходит для стека. Нам нужно закрывать скобки в обратном порядке: последняя открытая скобка должна закрыться первой.

Идея решения:

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

Если стек пуст, а мы встретили закрывающую скобку, значит закрывать нечего. Строка некорректна. Если тип скобки не совпал, строка тоже некорректна.

В конце стек должен быть пустым. Если в нем остались открывающие скобки, они не были закрыты.

Основные шаги:

  1. Создаем пустой стек.
  2. Создаем таблицу соответствий для закрывающих скобок:
")" -> "("
"]" -> "["
"}" -> "{"
  1. Идем по символам строки.
  2. Если символ открывающий, добавляем его в стек.
  3. Если символ закрывающий:
    • проверяем, что стек не пуст;
    • снимаем верхний элемент;
    • сравниваем его с ожидаемой открывающей скобкой.
  4. После цикла проверяем, что стек пуст.

Рассмотрим пример:

s = "([])"
  1. ( - кладем в стек: [(].
  2. [ - кладем в стек: [(, [].
  3. ] - верхушка стека [, она совпадает с ожидаемой.
  4. ) - верхушка стека (, она совпадает с ожидаемой.

Стек пуст, значит строка корректна.

Стек здесь хранит не все скобки, а только те открывающие скобки, которые еще не закрыты.

Оценка сложности

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

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

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

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

Код решения

Приведем код решения.

func isValid(s string) bool {
    pairs := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []rune{}
    for _, ch := range s {
        if expected, ok := pairs[ch]; ok {
            if len(stack) == 0 || stack[len(stack)-1] != expected {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, ch)
        }
    }
    return len(stack) == 0
}

Итоги

Скобки закрываются в порядке, обратном открытию, поэтому стек подходит идеально. Каждая открывающая скобка ждет свою пару на вершине стека, а каждая закрывающая скобка проверяет именно последнюю незакрытую.

Войдите чтобы отмечать прогресс