Я работаю над проблемой с Крекинг кодирвоание интервью, проблема +9,6 страница 110.Как построить футляр для n = 3 с использованием рекурсии снизу вверх?
Вот проблема:
Реализовать алгоритм для печати корректными (например, надлежащим образом открывались и закрывались комбинации п-пар . скобки Примеры
б (1) - "()"
б (2) - "(()),()()"
б (3) - «((())), (()())(),() (()),()()() «
Я пытаюсь использовать подход« снизу вверх », который автор обсуждает на стр. 107 -« Начнем с зная, как решить проблему для простого случая, например список с o один элемент и выяснить, как решить проблему для двух элементов, затем для трех элементов и т. д. Ключевым моментом здесь является, чтобы думать о том, как вы можете создать решение для одного случая от предыдущего случая»
Вот код, который я до сих пор
static void print(int n) {
print(n, new HashSet<String>(), "", "");
}
static void print(int n, Set<String> combs, String start, String end) {
if(n == 0) {
if(!combs.contains(start + end)) {
System.out.print(start + end);
combs.add(start + end);
}
} else {
print(n-1, combs, "(" + start, end +")");
System.out.print(", ");
print(n-1, combs, start, end + "()");
System.out.print(", ");
print(n-1, combs, "()" + start, end);
}
}
Чтобы получить этот код, я работал от (1), b (1), b (1) « Этот код действительно работает для первых двух случаев. Я действительно борется с в третьем случае. Может ли кто-нибудь дать мне подсказку (не весь ответ, может быть обращен к задней части книги для этого), о том, как перейти от случая 2 к делу 3 или, другими словами, использовать случай 2, чтобы добраться до case 3? Как, как бы вы перешли от (()),()() до
((())), (()()), (())(),() (()),()()()? Не могли бы вы отказаться от шаблона, который вы видели от b (1) до b (2), потому что он не работает для b (2) - b (3)?
С вашим алгоритмом как бы вы вынесете избыточность? – committedandroider
. Один из подходов состоит в том, чтобы иметь внутренний хэшсет, который хранит строковый шаблон, который вы сгенерировали до сих пор, всякий раз, когда вы создаете новую строку шаблона, вы должны проверить, присутствует ли такая строка шаблона в hashset, отбросить ее, если необходимо – chiwangc
Будет ли хороший Подход к вызову вашего перегруженного метода из моего в случае, если n> 1? Причина, по которой клиенту не нужно передавать эти данные. – committedandroider