Добрый день, не могу победить валидатор, на локальных наборах данных вроде работает, может подобрать набор где есть косяк.
package com.javarush.task.task22.task2209;
import java.io.*;
import java.util.*;
/*
Составить цепочку слов
*/
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String file = reader.readLine();
reader.close();
reader = new BufferedReader(new FileReader(file));
ArrayList<String> strArr = new ArrayList<>();
while (reader.ready())
strArr.add(reader.readLine());
ArrayList<String> arr = new ArrayList<>();
for (String s : strArr) {
Scanner scanner = new Scanner(s);
while (scanner.hasNext())
arr.add(scanner.next());
scanner.close();
}
reader.close();
String[] param = new String[arr.size()];
arr.toArray(param);
Object[] obj = arr.toArray();
StringBuilder result = getLine(param);
if (result != null)
System.out.println(result.toString());
}
/* public static StringBuilder getLine(String... words) {
StringBuilder result = new StringBuilder("");
if(words == null)
return null;
if(words.length == 0)
return null;
ArrayList<String> list = new ArrayList<>();
list.addAll(Arrays.asList(words));
ArrayList<String> used = new ArrayList<>();
used.add(list.get(0));
list.remove(0);
boolean flag = true;
while (list.size() > 0 && flag)
{
flag = false;
String str = used.get(used.size() - 1);
char last = str.charAt(str.length() - 1);
last = Character.toUpperCase(last);
for(int i = 0; i < list.size(); i++)
{
String s = list.get(i);
if(s.indexOf(last) == 0)
{
used.add(s);
list.remove(i);
flag = true;
break;
}
}
}
for (int i = 0; i < used.size(); i++)
{
result.append(used.get(i) + " ");
}
result.deleteCharAt(result.length() - 1);
return result;
}*/
public static StringBuilder getLine(String... words) {
StringBuilder result = new StringBuilder("");
if (words == null)
return result;
if (words.length == 0)
return result;
ArrayList<String> list = new ArrayList<>();
list.addAll(Arrays.asList(words));
Collections.sort(list);
List<String> max = null;
String word = null;
for (int i = 0; i < list.size(); i++) {
List<String> current = new ArrayList<>();
// Collections.copy(current, list);
current.addAll(list);
current.remove(i);
List <String> challenger = recursiveGetBigestChain(list.get(i), current);
if(challenger == null)
continue;
if(max == null) {
max = challenger;
word = list.get(i);
}
else if(max.size() < challenger.size()) {
max = challenger;
word = list.get(i);
}
}
if(max == null)
return null;
result.append(word + " ");
for (int i = 0; i < max.size(); i++) {
result.append(max.get(i) + " ");
}
result.deleteCharAt(result.length() - 1);
return result;
}
public static List<String> recursiveGetBigestChain(String word, List<String> list)
{
if(list.size() == 1 && word.toUpperCase().charAt(word.length() - 1) == list.get(0).charAt(0))
return list;
if (list.size() == 1)
return null;
List <String> max = null;
char last = Character.toUpperCase(word.charAt(word.length() - 1));
String curWord = "";
for(int i = 0; i < list.size(); i++)
{
if(last == list.get(i).charAt(0))
{
List<String> current = new ArrayList<>();
current.addAll(list);
current.remove(i);
List <String> challenger = recursiveGetBigestChain(list.get(i), current);
if(challenger == null)
continue;
if(max == null) {
max = challenger;
curWord = list.get(i);
}
else if(max.size() < challenger.size()) {
max = challenger;
curWord = list.get(i);
}
}
}
if(max == null || curWord == null)
return null;
List<String> res = new ArrayList<>();
res.add(curWord);
res.addAll(max);
return res;
}
public static void test() throws IOException
{
FileWriter writer = new FileWriter("d:\\1.txt");
writer.write("Киев Нью-Йорк Амстердам Вена Мельбурн");
writer.close();
}
}