Today I worked the problem out. As stated by @btilly, there are 9 cases to consider in every step.
Things to consider:
- It is necessary to check every possible change, as moving one string might look like a solution (greedy approach) but it might be a move that would imply the other words won't work for the palindrome.
- It is possible it is needed to make one move in every pair, meaning that no solution can be discarded beforehand.
The way to allow to diminish the amount of branches done doing a recursive approach is by being able to discard beforehand as much as possible, if we start with a pointer in the first element and one in the last element it is possible to just cut out from the recursion every branch that won't work as soon as possible.
In every step we will compare the left word being evaluated and the right word, if they are equal then we proceed with the inner words, if not, we need to check every case for the left word (word without changes, word taking a char from the next word, word giving the last char to the next word) against every possible case for the last word being evaluated (same cases as before, word without changes, word loosing its first char and word borrowing the last char from the second to last word), and for every case that does make it palindrome we should recursively try with the rest of the words moving to the middle (left++ and right--). If we arrive to the case in which there is no words left or just one word left, then we arrived to a palindrome.
The code is quite extensive to write, here is my solution:
public class WordsPalindromes {
public static boolean solution(String[] arr) {
return makePalindrome(Arrays.asList(arr));
}
public static boolean makePalindrome(List<String> words){
if(words.size()==0 || words.size()==1)
return true;
if(words.size()==2){
return words.get(0).equals(words.get(1)) ||
words.get(0).substring(0,words.get(0).length()-1).equals(words.get(0).substring(words.get(0).length()-1)+words.get(1)) ||
(words.get(0)+words.get(1).substring(0,1)).equals(words.get(1).substring(1));
}
boolean result = false;
String first = words.get(0);
String last = words.get(words.size()-1);
String second = words.get(1);
String secondLast = words.get(words.size()-2);
int wSize = words.size();
if(first.equals(last)){
List<String> filtered =copy(words, 1, wSize-1);
result = result||makePalindrome(filtered);
}
String firstShort = first.substring(0,first.length()-1);
String secondLong = first.charAt(first.length()-1) + second;
String firstLong = first + second.charAt(second.length()-1);
String secondShort = second.substring(1);
String lastShort = last.substring(1);
String secondLastLong = secondLast + last.charAt(0);
String lastLong = secondLast.substring(secondLast.length()-1) + last;
String secondLastShort = secondLast.substring(0,secondLast.length()-1);
if(firstShort.equals(last)){
List<String>filtered = copy(words, 1,wSize-1);
filtered.add(0,secondLong);
result = result||makePalindrome(filtered);
}
if(firstShort.equals(lastShort)){
List<String>filtered = copy(words, 2,wSize-2);
filtered.add(0,secondLong);
filtered.add(secondLastLong);
result = result||makePalindrome(filtered);
}
if(firstShort.equals(lastLong)){
List<String>filtered = copy(words, 2,wSize-2);
filtered.add(0,secondLong);
filtered.add(secondLastShort);
result = result||makePalindrome(filtered);
}
if(first.equals(lastShort)){
List<String>filtered = copy(words, 1,wSize-2);
filtered.add(secondLastLong);
result = result||makePalindrome(filtered);
}
if(first.equals(lastLong)){
List<String>filtered = copy(words, 1,wSize-2);
filtered.add(secondLastShort);
result = result||makePalindrome(filtered);
}
if(firstLong.equals(last)){
List<String>filtered = copy(words, 2,wSize-1);
filtered.add(0,secondShort);
result = result||makePalindrome(filtered);
}
if(firstLong.equals(lastShort)){
List<String>filtered = copy(words, 2,wSize-2);
filtered.add(0,secondShort);
filtered.add(secondLastLong);
result = result||makePalindrome(filtered);
}
if(firstLong.equals(lastLong)){
List<String>filtered = copy(words, 2,wSize-2);
filtered.add(0,secondShort);
filtered.add(secondLastShort);
result = result||makePalindrome(filtered);
}
return result;
}
public static List<String> copy(List<String> elements, int start, int end){
List<String> result = new ArrayList<String>();
for(int i=start;i<end;i++ ){
result.add(elements.get(i));
}
return result;
}
}
This solution performance can be improved by avoiding copying the list in every step, and use indexes instead.
