C
Hier der korriegierte Code fuer den breadth first Search. Hatte nee for schleife zuviel drin
//Wordladder.java
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
public class Wordladder {
String [] dictionary = new String[]{"tears","spile","spars","teari","lears","sears","spire","spare","smile"};
String startWord = "tears";
String endWord = "smile";
Queue<ArrayList<String>> queue = new LinkedList<ArrayList<String>>();
public Wordladder()
{
bfs();
}
public void bfs()
{
ArrayList<String> root = new ArrayList<String>();
root.add(startWord);
queue.add(root);
while(!queue.isEmpty())
{
ArrayList<String> current = queue.remove();
for(int j = 0 ; j < dictionary.length;j++) // process dictionary for each queue
{
if( isNeighbor(current.get(current.size()-1),dictionary[j]) )
{
if(current.get(current.size()-1).equals(endWord))
{
String ausgabe = "";
for(int k = 0 ; k< current.size();k++)
{
if(k < current.size()-1)
ausgabe +=current.get(k)+" - ";
else
ausgabe +=current.get(k);
}
System.out.println("Wordladder");
System.out.println(ausgabe);
break;
}
if(!current.contains(dictionary[j]))
{
ArrayList<String> partialLadder = new ArrayList<String>(current.size()+1);
copyArrayList(current, partialLadder);
partialLadder.add(dictionary[j]);
queue.add(partialLadder);
}
}
}
}
}
public boolean isNeighbor(String str1, String str2)
{
int count = 0;
for(int i =0;i < str1.length();i++)
{
if(str1.charAt(i) != str2.charAt(i) )
{
count++;
}
if(count >1 || (str1.length() != str2.length()))
{
return false;
}
}
return true;
}
private void copyArrayList(ArrayList<String> src, ArrayList<String> dst)
{
for(int i = 0;i < src.size();i++ )
{
dst.add(src.get(i));
}
}
}