Не могу побороть 5,6 пункт
Все известные здесь тесты решает бытро, находит максимально длинную цепь, выводит первую из найденных. Но перебирает все варианты.
package com.javarush.task.task22.task2209;
import java.util.ArrayList;
import java.util.List;
public class Graf {
public static List<String> words = new ArrayList<>();//исходный набор слов
public static List<String> bestChain = new ArrayList<>();// лучшая (самая длинная) найденная цепь
public static List<String> chain = new ArrayList<>();// текущая цепь во время вычислений
public static List<Boolean> wordInChain = new ArrayList<>(); //маркер использования слова в цепи
public Graf(String... words) {
for (String s: words){
this.words.add(s);
wordInChain.add(false);
}
}
public static void findBestChain(){
for (String s:words) {
findNextElement(s);
}
}
public static void findNextElement (String s){
wordInChain.set(words.indexOf(s), true); // слово уже использовано
//добавляем слово в цепь
chain.add(s);
for (int i = 0; i < words.size(); i++) {
if (wordInChain.get(i)) continue; // слово уже использовано?
//если начало следующего слова совпадает с концом переданного в метод
String s1 = s.substring(s.length() - 1);
String s2 = words.get(i).substring(0, 1);
if (s1.equalsIgnoreCase(s2)) {
findNextElement(words.get(i)); //рекурсия
}
}
setNewBestChain();
wordInChain.set(words.indexOf(s), false);
chain.remove(chain.size() - 1);
}
public static void setNewBestChain (){
if (chain.size() > bestChain.size()) {
bestChain = new ArrayList<>(chain);
}
}
}