I have an ArrayList which contains Strings with a size of 1000. I am looping through that ArrayList and finding words and trying to form a square from them. For example as follows:
C A R D
A R E A
R E A R
D A R T
The square must match left to right and top to bottom. So first left to right word (card) must match first top to bottom (card) and so on. The list has [voes, rose, soon, odds] and so on, a 1000 of them all of length 4.
I am looping through them 1 by 1. So take 'voes' first, loop through remaining 999, find the first word starting with 'o', i store it as second word (example: odds) and move on to next loop.
This will give me for example:
voes
odds
loop 999 times again. first letter to start with 'e' and its 3rd letter is 'd' store that as 3rd name and move on to 4th loop.
This will give me for example:
voes
odds
eddo
loop 999 times again. Similar check for 4th word. And lets say I cant find any word that meets the condition. Break out of loop, go on top and replace the first word to the second word in the list and do it all over again.
I have managed to get it working but it involves a lot of nested looping. If I am reading this right, this is O(n^4). Is there a more efficient way to do this.
void makeWord(ArrayList<String> arr){
String first, second, third, fourth;
for (int i = 0; i < arr.size(); i++) {
first = arr.get(i);
for (int j = 0; j < arr.size(); j++) {
if(first.substring(1,2).equals(arr.get(j).substring(0,1)) &&
(!first.equals(arr.get(j)))){
second = arr.get(j);
}
else {
second = " ";
}
if (!second.trim().isEmpty()) {
for (int k = 0; k < arr.size(); k++) {
if (first.substring(2, 3).equals(arr.get(k).substring(0, 1)) &&
second.substring(2, 3).equals(arr.get(k).substring(1, 2)) &&
(!first.equals(arr.get(k)) && (!second.equals(arr.get(k))))) {
third = arr.get(k);
} else {
third = " ";
}
if (!third.trim().isEmpty()) {
for (int m = 0; m < arr.size(); m++) {
if(first.substring(3,4).equals(arr.get(m).substring(0,1)) &&
second.substring(3,4).equals(arr.get(m).substring(1,2))&&
third.substring(3,4).equals(arr.get(m).substring(2,3)) &&
(!first.equals(arr.get(m)) && (!second.equals(arr.get(m))))){
fourth = arr.get(m);
}
else {
fourth = " ";
}
if (!(fourth.trim().isEmpty())) {
System.out.println(first);
System.out.println(second);
System.out.println(third);
System.out.println(fourth);
System.out.println(" ");
}
}
}
}
}
}
}
}