Под корректными комбинациями пар будем понимать правильно открытые и закрытые скобки. На вход подаётся число пар скобок, на выходе должны быть все возможные их комбинации в виде набора строк.
Первая мысль — использовать рекурсивный подход, который строит решение для f(n), добавляя пары круглых скобок в f(n-1). Это, конечно, правильная мысль.
Рассмотрим решение для n = 3:
(()()) ((())) ()(()) (())() ()()()
Как получить это решение из решения для n = 2?
(()) ()()
Можно расставить пары скобок в каждую существующую пару скобок, а также одну пару в начале строки. Другие места, куда мы могли вставить скобки, например в конце строки, получатся сами собой.
Итак, у нас есть следующее:
(()) -> (()()) /* скобки вставлены после первой левой скобки */
-> ((())) /* скобки вставлены после второй левой скобки */
-> ()(()) /* скобки вставлены в начале строки */
()() -> (())() /* скобки вставлены после первой левой скобки */
-> ()(()) /* скобки вставлены после второй левой скобки */
-> ()()() /* скобки вставлены в начале строки */Но постойте! Некоторые пары дублируются! Строка ()(()) упомянута дважды! Если мы будем использовать данный подход, то нам понадобится проверка дубликатов перед добавлением строки в список. Реализация такого метода выглядит так:
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;
}Алгоритм работает, но не очень эффективно. Мы тратим много времени на дублирующиеся строки.
Избежать проблемы дублирования можно путем построения строки с нуля. Этот подход подразумевает, что мы добавляем левые и правые скобки, пока наше выражение остается правильным.
При каждом рекурсивном вызове мы получаем индекс определенного символа в строке. Теперь нужно выбрать скобку (левую или правую). Когда использовать левую скобку, а когда — правую?
- Левая скобка: пока мы не израсходовали все левые скобки, мы можем вставить левую скобку.
- Правая скобка: мы можем добавить правую скобку, если добавление не приведет к синтаксической ошибке. Когда появляется синтаксическая ошибка? Тогда, когда правых скобок больше, чем левых.
Таким образом, нам нужно отслеживать количество открывающих и закрывающих скобок. Если в строку можно вставить левую скобку, добавляем ее и продолжаем рекурсию. Если левых скобок больше, чем правых, то вставляем правую скобку и продолжаем рекурсию.
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-компанию».
Как Яндекс использует ваши данные и машинное обучение для персонализации сервисов — читать и смотреть YaC 2019.
