Валидация скобочной последовательности (3 вида скобок)

Легкая

easy , string , stack

20 September 2023

Описание задачи #

Напишите функцию, которая будет проверять скобочную последовательность на валидность.

Входные данные: строка, состоящая из скобок.

Выходные данные: bool

О том, что такое правильная скобочная последовательность можно прочитать в статье на википедии.

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

В строке может содержаться от 1 до 10⁴ символов
Строка состоит только из скобок (, ), [, ], {, }

Примеры #

Входные данные: ()

Ответ: true
Входные данные: ()[]{}

Ответ: true
Входные данные: (]

Ответ: false

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

Скобочная последовательность является валидной если:

Все открытые скобки имеют закрывающую скобку
Все открытые скобки закрываются в правильном порядке (сперва идет открывающая скобка, только после нее закрывающая)
Все открытые скобки закрываются соответствующим типом закрывающих скобок ( -> ), [ -> ], { -> }
В строке не может быть закрывающих скобок без предшествующих открывающих

Решение #

Данная задача имеет «каноническое» оптимальное решение, которое ожидается на любом интервью (хотя, конечно, это не единственно верное решение). В этом решении используется структура данных стек.

Алгоритм:

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

package main

func isValid(brackets string) bool {
	stack := make([]rune, 0, len(brackets))

	closeBracket := map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
	}

	for _, char := range brackets {
		if openBracket, isClose := closeBracket[char]; isClose {
			if len(stack) == 0 {
				return false
			}

			lastOpenBracket := stack[len(stack)-1]

			if lastOpenBracket != openBracket {
				return false
			}

			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, char)
		}
	}

	return len(stack) == 0
}

export const isValid = (brackets: string): boolean => {
    const stack: string[] = []

    const closeBrackets: Record<string, string> = {
        ')': '(',
        ']': '[',
        '}': '{',
    }

    for (let i = 0; i < brackets.length; i++) {
        const char = brackets[i]
        const openBracket = closeBrackets[char]

        if (openBracket) {
            if (stack.length === 0) {
                return false
            }

            const lastOpenBracket = stack[stack.length - 1]

            if (lastOpenBracket !== openBracket) {
                return false
            }

            stack.pop()
        } else {
            stack.push(char)
        }
    }

    return stack.length === 0
}

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

По времени

Сложность O(n), где n — длина строки.

По памяти

Сложность O(n), так как для валидации последовательности нам нужно выделить память под стек, который в худшем случае равен длине строки.

Оригинал задачи на Leetcode

Algorithmics