# Test "cet", "ism" test takes forever to run.

• On the "cet", "ism" test case, I am running it forever. I am using a BFS approach. I have outlined the algorithm in comments

``````// check if there is such a word to get from the dict to the end
Boolean wordExists = false;
for (String s : dict) {
Integer difference = 0;
for (int idx = 0; idx < end.length(); idx ++) {
if (s.charAt(idx) != end.charAt(idx)) {
difference ++;
}
}
if (difference == 1) {
// there is such a word
//System.out.println(s);
wordExists = true;
break;
}
}

if (!wordExists) {
return new ArrayList<ArrayList<String>>();
}

ArrayList<ArrayList<String>> toReturn = new ArrayList<ArrayList<String>>();
Boolean reachedDestination = false;
Integer shortestDistance = -1;
/*
* For each popped ladder, get the last string and see if it is
* 1 distance away from the end.
* If it is, then we have reached our destination. Find all the ladders where the last string is 1 away
* from the end.
* If it isn't, then check if there exists a
* word in the dictionary that is 1 away from it.
* If there is such a word, then spawn a new ladder and insert
* it to ladders queue. Remove the word from the corresponding dictionary, make a new dictionary and add that to the dictionaries queue.
*/
HashSet<String> currDict = dicts.remove();
/*
* Check if the lastString is 1 away from the end
*/
Integer differenceToEnd = 0;
for (int idx = 0; idx < end.length(); idx ++) {
if (lastString.charAt(idx) != end.charAt(idx)) {
differenceToEnd ++;
}
}
if (differenceToEnd == 1) {
// Reached the destination
if (shortestDistance < 0) {
reachedDestination = true;
} else if (currLadder.size() == shortestDistance) {
}
} else if (reachedDestination && currLadder.size() > shortestDistance) {
// We are done here.
} else if (differenceToEnd > 1 && !reachedDestination) {
for (int idx = 0; idx < lastString.length(); idx ++) {
char[] currentStringCharArray = lastString.toCharArray();
for (char c = 'a'; c <= 'z'; c ++) {
currentStringCharArray[idx] = c;
String newString = new String(currentStringCharArray);
/* Calculate difference from newString to end */
Integer newDiffToEnd = 0;
for (int ind = 0; ind < end.length(); ind ++) {
if (newString.charAt(ind) != end.charAt(ind)) {
newDiffToEnd ++;
}
}
if (!newString.equals(start) && (newDiffToEnd <= differenceToEnd)) {
if (currDict.contains(newString)) {
@SuppressWarnings("unchecked")
currDict.remove(newString);
@SuppressWarnings("unchecked")
HashSet<String> newDict = (HashSet<String>)currDict.clone();
System.out.println("queue size = " + ladders.size());
}
}
}
}
}
}