01.05 Позитивные технологии
01.05 Позитивные технологии
01.05 Позитивные технологии

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

Аватар Типичный программист
Отредактировано

15К открытий15К показов

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

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

Следите за новыми постами
Следите за новыми постами по любимым темам
15К открытий15К показов