Под корректными комбинациями пар будем понимать правильно открытые и закрытые скобки. На вход подаётся число пар скобок, на выходе должны быть все возможные их комбинации в виде набора строк.
Первая мысль — использовать рекурсивный подход, который строит решение для f(n), добавляя пары круглых скобок в f(n-1). Это, конечно, правильная мысль.
Рассмотрим решение для n = 3:
(()()) ((())) ()(()) (())() ()()()
Как получить это решение из решения для n = 2?
(()) ()()
Можно расставить пары скобок в каждую существующую пару скобок, а также одну пару в начале строки. Другие места, куда мы могли вставить скобки, например в конце строки, получатся сами собой.
Итак, у нас есть следующее:
1 2 3 4 5 6 | (()) -> (()()) /* скобки вставлены после первой левой скобки */ -> ((())) /* скобки вставлены после второй левой скобки */ -> ()(()) /* скобки вставлены в начале строки */ ()() -> (())() /* скобки вставлены после первой левой скобки */ -> ()(()) /* скобки вставлены после второй левой скобки */ -> ()()() /* скобки вставлены в начале строки */ |
Но постойте! Некоторые пары дублируются! Строка ()(()) упомянута дважды! Если мы будем использовать данный подход, то нам понадобится проверка дубликатов перед добавлением строки в список. Реализация такого метода выглядит так:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | public static Set<String> generateParens(int remaining) { Set<String> set = new HashSet<String>(); if (remaining == 0) { set.add(""); } else { Set<String> prev = generateParens(remaining - 1); for (String str : prev) { for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '(') { String s = insertInside(str, i); if (!set.contains(s)) { set.add(s); } } } if (!set.contains("()" + str)) { set.add("()" + str); } } } return set; } public String insertInside(String str, int leftIndex) { String left = str.substring(0, leftIndex + 1); String right = str.substring(leftIndex + 1, str.length(); return left + "()" + right; } |
Алгоритм работает, но не очень эффективно. Мы тратим много времени на дублирующиеся строки.
Избежать проблемы дублирования можно путем построения строки с нуля. Этот подход подразумевает, что мы добавляем левые и правые скобки, пока наше выражение остается правильным.
При каждом рекурсивном вызове мы получаем индекс определенного символа в строке. Теперь нужно выбрать скобку (левую или правую). Когда использовать левую скобку, а когда — правую?
- Левая скобка: пока мы не израсходовали все левые скобки, мы можем вставить левую скобку.
- Правая скобка: мы можем добавить правую скобку, если добавление не приведет к синтаксической ошибке. Когда появляется синтаксическая ошибка? Тогда, когда правых скобок больше, чем левых.
Таким образом, нам нужно отслеживать количество открывающих и закрывающих скобок. Если в строку можно вставить левую скобку, добавляем ее и продолжаем рекурсию. Если левых скобок больше, чем правых, то вставляем правую скобку и продолжаем рекурсию.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | public void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) { if (leftRem < 0 || rightRem < leftRem) return; // некорректное состояние if (leftRem == 0 && rightRem == 0) { /* нет больше левых скобок */ String s = String.copyValueOf(str); list.add(s); } else { /* Добавляем левую скобку, если остались любые левые скобки */ if (leftRem > 0) { str[count] = '('; addParen(list, leftRem - 1, rightRem, str, count + 1); } /* Добавляем правую скобку, если выражение верно */ if (rightRem > leftRem) { str[count] = ')'; addParen(list, leftRem, rightRem - 1, str, count + 1); } } } public ArrayList<String> generateParens(int count) { char[] str = new char[count * 2]; ArrayList<String> list = new ArrayList<String>(); addParen(list, count, count, str, 0); return list; } |
Поскольку мы добавляем левые и правые скобки для каждого индекса в строке, индексы не повторяются, и каждая строка гарантированно будет уникальной.
Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».