Generate Parentheses

Средняя№22счёт скобок

Дано число n. Нужно вернуть все строки из n "(" и n ")", в которых скобки расставлены правильно: если читать слева, ")" никогда не идёт, когда все "(" перед ней уже закрыты. Наш пример: n = 2 даёт 2 строки, "(())" и "()()".

22 Generate ParenthesesРазбор · 1×

Пример: все правильные строки из 2 пар. Смотрите на отрезанные ветки: в корне ")" не пускается, потому что ещё ничего не открыто, а в "((" — третья "(", потому что обе уже стоят.

""((((()(())()()(()()s—open–close–n = 2результаты—
ещё не былипо пути сюдаэтот шаг; счётчик пускает скобкуотрезано: счётчик не пускает скобкусохранённая строказавершено

Строим все правильные строки из 2 пар скобок

01/28
сначала · назад · пуск · шаг
Скорость
1function generateParenthesis(n):
2 results = []
3 build('', 0, 0)
4 return results
5
6function build(s, open, close):
7 if len(s) == 2 * n:
8 add s to results
9 return
10 if open < n: // room for one more (
11 build(s + '(', open + 1, close)
12 if close < open: // a ( is still not closed
13 build(s + ')', open, close + 1)
состояние
s
–
open
–
close
–
results
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. ")" добавляется, только пока close < open, поэтому в любой точке строки перед ней ")" не больше, чем "(": по пути строка не может испортиться.
  2. "(" добавляется, только пока open < n, поэтому больше n таких скобок в строке не бывает; когда в ней 2n скобок, open = close = n, и она правильная.
  3. Каждая правильная строка находится: на каждом месте в ней стоит "(" или ")", которую счётчики разрешают, а прогон пробует обе. В запрещённые ветки прогон не заходит, поэтому в конце ничего проверять не нужно.

Сложность

Время O(√n × 4ⁿ): всего счётчики пропускают O(4ⁿ / √n) начал строк (они растут как числа Каталана), и каждый вызов собирает свою строку за 2n шагов. Память O(n²) помимо ответа: стек вызовов глубиной 2n, и у каждого вызова своя строка до 2n скобок.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.