Алгоритм, выводящий все корректные комбинации пар круглых скобок

13982

Под корректными комбинациями пар будем понимать правильно открытые и закрытые скобки. На вход подаётся число пар скобок, на выходе должны быть все возможные их комбинации в виде набора строк.

Первая мысль — использовать рекурсивный подход, который строит решение для 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;
}

Алгоритм работает, но не очень эффективно. Мы тратим много времени на дублирующиеся строки.

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

При каждом рекурсивном вызове мы получаем индекс определенного символа в строке. Теперь нужно выбрать скобку (левую или правую). Когда использовать левую скобку, а когда — правую?

  1. Левая скобка: пока мы не израсходовали все левые скобки, мы можем вставить левую скобку.
  2. Правая скобка: мы можем добавить правую скобку, если добавление не приведет к синтаксической ошибке. Когда появляется синтаксическая ошибка? Тогда, когда правых скобок больше, чем левых.

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

			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-компанию».

13982