Задача на работу со скобками

Отредактировано

Задача на построение алгоритма для вывода всех корректных (правильно открытых и закрытых) комбинаций из n пар круглых скобок.

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

Условие задачи

Реализуйте алгоритм для вывода всех корректных (правильно открытых и закрытых) комбинаций из n пар круглых скобок.

Пример:

Ввод: 3
Вывод: ( ( () ) ), ( ()() ), ( () )(), ()( () ), ()()()

Решение

Первое, что приходит в голову, — использовать рекурсивный подход и строить решение для f(n), добавляя пары круглых скобок в f(n-1). Мысль абсолютно здравая.

Рассмотрим решение для n = З:

			( () () )  (( () ))  ()( () )   ( () ) ()  ()()()

Как получить это решение из решения для n = 2?

			( () )  () ()

Можно вставить пары скобок в каждую существующую пару скобок, а также одну пару в начале строки. Другие возможные места для вставки скобок (например, в конце строки) сводятся к предыдущим случаям.

Итак, имеем следующее:

			( () ) -> ( ()() ) /* скобки вставлены после первой левой скобки */
-> (( () )) /* скобки вставлены после второй левой скобки */
-> ( ) ( () ) /* скобки вставлены в начале строки */
( ) ( ) -> ( () )() /* скобки вставлены после первой левой скобки */
-> ( ) ( ( ) ) /* скобки вставлены после второй левой скобки */
- > () () () /* скобки вставлены в начале строки */

Постойте, в списке есть дубликаты! Строка () ( () ) встречается дважды! Если мы будем использовать данный подход, следует реализовать проверку дубликатов перед добавлением строки в список.

			import java.util.HashSet;
import java.util.Set;

public class QuestionA {
	public static 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 static Set generateParens(int remaining) {
		Set set = new HashSet();
		if (remaining == 0) {
			set.add("");
		} else {
			Set 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);
						/ * Добавить строку s в множество, если ее там нет . Примечание :
                                                  * HashSet автоматически проверяет дубликаты перед
                                                  * добавлением, так что явная проверка окажется лишней . */
						set.add(s);			
					}
				}
				set.add("()" + str);
			}
		}
		return set;
	}
	
	public static void main(String[] args) {
		Set list = generateParens(4);
		for (String s : list) {
			System.out.println(s);
		}
		System.out.println(list.size());
	}

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

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

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

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

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

			import java.util.ArrayList;

public class QuestionB {
	
	public static void addParen(ArrayList list, int leftRem, int rightRem, char[] str, int index) {
		if (leftRem < 0 || rightRem < leftRem) return; // Некорректное состояние
		
		if (leftRem == 0 && rightRem == 0) { /* Скобок не осталось */
			list.add(String.copyValueOf(str));
		} else {
			str[index] = '('; /* Добавить левую скобку, если они еще остались . */
			addParen(list, leftRem - 1, rightRem, str, index + 1);
			
			str[index] = ')'; /* Добавить правую скобку, если выражение корректно */
			addParen(list, leftRem, rightRem - 1, str, index + 1);
		}
	}
	
	public static ArrayList generateParens(int count) {
		char[] str = new char[count*2];
		ArrayList list = new ArrayList();
		addParen(list, count, count, str, 0);
		return list;
	}
	
	public static void main(String[] args) {
		ArrayList list = generateParens(6);
		for (String s : list) {
			System.out.println(s);
		}
		System.out.println(list.size());		
	}

Поскольку мы добавляем левые и правые скобки для каждого индекса в строке, индексы не повторяются, и каждая строка гарантированно будет уникальной .

Задачи умеренной сложностиПодписаться

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

Также рекомендуем

7 легендарных уравнений на JavaScript

Математика и компьютерные науки идут рука об руку. Подобрали 7 математических формул разного уровня сложности для проверки — сможете ли вы их реализовать? И на всякий случай снабдили статью нашими решениями.

IT-задачи о кофе, switch и шумах

Собрали самые каверзные задачи на тему программирования по Go, C# и QA, которые удивили инженеров Ozon Tech, и делимся решениями.

Логические задачи для программистов, которые бесят своей простотой

Собрали каверзные логические задачи с собеседований для SDE. Они кажутся сложными, но на деле довольно простые. Испытайте себя!

7 математических задач на LeetCode для продвинутых

Собрали несколько математических задач высокого уровня сложности и добавили варианты решения на Python.