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

Средняя

medium , string , backtracking

24 September 2023

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

Напишите функцию, которая будет генерировать все возможные валидные скобочные последовательности длиной 2n.

Входные данные: int — количество пар скобок.

Выходные данные: массив строк — все возможные валидные скобочные последовательности длиной 2n.

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

1 <= n <= 8

Примеры #

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

Ответ: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Входные данные: 1

Ответ: ["()"]

Брутфорс решение #

Давайте разобьем задачу на 2 подзадачи:

генерация всех возможных строк длиной 2n, состоящих из символов ( и );
проверка строк на то, что они являются валидными скобочными последовательностями.

Генерация всех возможных строк длиной 2n, состоящих из символов «(» и «)» #

Достаточно тривиальная задача:

Создаем исходный массив. В нашем случае из одного элемента, так как валидная скобочная последовательность может начинаться только с открывающей скобки.
Запускаем цикл до 2 * n, где n — количество пар скобок.
В каждой итерации цикла проходимся по всем элементам предыдущего результата и добавляем 2 новых варианта с открывающей и закрывающей скобками.

func generateAllPossibleParenthesis(n int) []string {
    combinations := make([]string, 0, 100)
    combinations = append(combinations, "(")
    
    for i := 1; i < n*2; i++ {
        newArray := make([]string, 0, len(combinations))
        for _, item := range combinations {
            newArray = append(newArray, item+"(")
            newArray = append(newArray, item+")")
        }
        
        combinations = newArray
    }
    
    return combinations
}

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

Эту задачу мы уже разбирали. Чтобы не повторяться, возьмем готовое решение для проверки валидности скобочной последовательности.

В результате получим следующие решения.

package main

func generateParenthesisBruteforce(n int) []string {
	combinations := generateAllPossibleParenthesis(n)
	res := make([]string, 0, len(combinations))
	for _, parenthesis := range combinations {
		if !isValid(parenthesis) {
			continue
		}

		res = append(res, parenthesis)
	}

	return res
}

func generateAllPossibleParenthesis(n int) []string {
	combinations := make([]string, 0, 100)
	combinations = append(combinations, "(")

	for i := 1; i < n*2; i++ {
		newArray := make([]string, 0, len(combinations))
		for _, item := range combinations {
			newArray = append(newArray, item+"(")
			newArray = append(newArray, item+")")
		}

		combinations = newArray
	}

	return combinations
}

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 function generateParenthesisBruteforce(n: number): string[] {
	const combinations = generateAllPossibleParenthesis(n)
	let res: string[] = []

	combinations.forEach((parenthesis) => {
		if (isValid(parenthesis)) {
			res.push(parenthesis)
		}
	})

	return res
}

function generateAllPossibleParenthesis(n: number): string[] {
	let combinations: string[] = ["("]

	for (let i = 1; i < n * 2; i++) {
		const newArray: string[] = []

		combinations.forEach((item) => {
			newArray.push(item + "(")
			newArray.push(item + ")")
		})

		combinations = newArray
	}

	return combinations
}

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). В нашем случае все строки имеют длину 2n, но итоговая сложность все равно будет равна O(n).

Давайте оценим количество сгенерированных строк. Каждый элемент строки кроме первого — произвольный символ из множества ["(", ")"], а количество символов в итоговой строке 2 * n. Таким образом, кол-во строк равно 2²ⁿ.

Итоговую сложность мы можем оценить как n * (2²ⁿ).

По памяти

Самый большой расход памяти в нашем случае — хранение всех возможных строк. Для этого нам понадобится массив строк, размером 2²ⁿ, каждый элемент которого равен 2 * n. То есть мы можем говорить о n * 2²ⁿ дополнительной памяти.

Чаще всего, в задачах с комбинаторикой решение с полным перебором всех возможных вариантов является сильно не оптимальным, так как скорость роста сложности решения относительно размера входных данных очень высока. Так в этой задаче при n = 8 кол-во всех возможных вариантов строк — 32768 (2¹⁵).

Оптимизированный брутфорс #

Основная проблема брутфорс решения — генерация большого количества заведомо невалидных строк. Это можно исправить если мы перед добавлением очередного символа добавим проверки, откидывающие заведомо невалидные символы.

Задача сильно упрощается тем, что в условии сказано, что скобки могут быть только одного типа — круглые. В этом случае мы можем использовать для валидации последовательности обычный счетчик. Давайте опишем правила, когда мы можем добавлять разные скобки:

Открывающую скобку мы можем добавить, если суммарное количество открытых скобок в строке не превышает числа n и если открывающих скобок в строке не меньше закрывающих.
Закрывающую скобку мы можем добавить, если суммарное количество открытых скобок в строке больше чем закрывающих.

В этом решении не нужно постфактум проверять получившиеся скобки на валидность, так что мы сможем отбросить один из множителей в нашей оценке сложности.

package main

func generate(n int, row string, opened int, closed int, answer *[]string) {
	if len(row) == n*2 {
		*answer = append(*answer, row)
		return
	}

	if opened >= closed && opened < n {
		generate(n, row+"(", opened+1, closed, answer)
	}

	if opened > closed {
		generate(n, row+")", opened, closed+1, answer)
	}
}

func generateParenthesis(n int) []string {
	res := make([]string, 0)
	generate(n, "(", 1, 0, &res)

	return res
}

export const generate = (n: number, row: string, opened: number, closed: number, answer: string[]): void => {
    if (row.length === n * 2) {
        answer.push(row)
        return
    }

    if (opened >= closed && opened < n) {
        generate(n, row + "(", opened + 1, closed, answer)
    }

    if (opened > closed) {
        generate(n, row + ")", opened, closed + 1, answer)
    }
}

export const generateParenthesis = (n: number): string[] => {
    const res: string[] = []
    generate(n, "(", 1, 0, res)
    return res
}

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

По времени

В данном решении не нужна валидация последовательности. Ее мы заменили на проверку допустимости добавления открывающей/закрывающей скобки в момент генерации строки. Более того, за счет сохранения счетчика суммарного количества открытых и счетчика незакрытых скобок мы можем проводить эту проверку за константное время.

Количество сгенерированных строк равно 2^2n-1.

На самом деле количество строк сильно меньше, так как мы заранее отбрасываем все невалидные скобочные последовательности. Но, оценить их количество сильно сложнее. Валидно будет сказать, что в худшем случае сложность O(2^2n-1).

По памяти

Нам нужно выделить память для хранения всех результирующих строк. Каждая строка имеет длину 2*n. Также, как и в оценке по сложности, валидно сказать, что количество строк сравнимо с 2^2n-1.

Таким образом, сложность по памяти равна O(n * 2^2n-1).

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

Algorithmics

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

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

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

Примеры #

Брутфорс решение #

Генерация всех возможных строк длиной 2n, состоящих из символов «(» и «)» #

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

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

Оптимизированный брутфорс #

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