Учебная записка [Medium] Leetcode#22 Generate Parentheses

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

Описание задачи выглядит следующим образом.

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

Пример 1:

Input: n = 1
Output: ["()"]

Пример 2:

Input: n = 2
Output: ["()()","(())"]

Пример 3:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Давайте понаблюдаем за шаблоном генерации на примере небольших случаев.

Для n = 0, очевидно, это тривиальный случай [] # пустой список

Для n = 1, только один допустимый вывод ["()"].

Для n = 2, мы можем рассматривать n = 2 как своего рода эволюцию от n = 1.

На этот раз мы должны составить еще одну пару на основе n = 1

Форма генерации может быть переписана как ( + preStr ) + postStr, где

PreStr содержит i пар, причем одна куртка () вносит одну пару. А postStr вносит n-1-i пар.

Таким образом, мы имеем

()(), в котором мы заключаем исходную строку с еще одной парой вне preStr как пустой строки, а также postStr как (), или

( () ), в которую мы заключаем исходную строку с еще одной парой вне preStr как (), а также postStr как пустую строку.

Два допустимых вывода для n= 2

["()()", "(())"]

Для n = 3 мы можем рассматривать n = 3 как своего рода эволюцию от n = 2

Опять же, мы должны составить еще одну пару на основе n = 2

Напомним, что форма генерации может быть переписана как ( + preStr ) + postStr, где

PreStr содержит i пар, причем одна куртка вносит одну пару. А postStr вносит n-1-i пар.

Таким образом, мы имеем

() ()(), и () (()), которые мы заключаем исходную строку с еще одной парой вне preStr как пустую строку и postStr как ()() и (()), или

() () ) (), в которые мы заключаем исходную строку с еще одной парой вне preStr как () и postStr как (), или

( ()() ), и ( (()) ), которые мы заключаем в исходную строку с еще одной парой снаружи preStr как ()() и (()) и postStr как ()() и (()).

Пять допустимых выходов для n= 3

["((()))","(()())","(())()","()(())","()()()"]

Теперь у нас есть общая картина шаблона допустимой пары скобок.

Давайте реализуем его в Python.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        # memoization
        memo = {
            # base case
            0: [""],
            1: ["()"]
        }

        
        def gen(n: int):
            
            # look up table
            if n in memo:
                return memo[n]

            # general cases:
            # preStr contribute i pairs,
            # () jacket contribute 1 pair,
            # postStr contibutes (n-1-i) pairs
            memo[n] = [ "(" + preStr + ")" + postStr for i in range(n) for preStr in gen(i) for postStr in gen(n-1-i) ]
            return memo[n]

        # ---------------------
        return gen(n)

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

O( 4^n/ sqrt(n) ), это то же самое, что и n-ое каталанское число .

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

O( 4^n/ sqrt(n) ), это то же самое, что и n-ое каталанское число .

Подробный вывод верхней границы для n-го каталанского числа можно найти здесь.

Ссылка:

[1] Leetcode #22 Generate brackhes