I am writing a program that is supposed to read a file of words and then find the shortest from one word to another by going from the startword to an adjacent word that will differ with one letter, simple example: Startword: dog endword: for could be: " dog -> fog -> for".
My idea is to do a BFS in a adjacent list. Everything is working in my code except for my Graph (adjacent list). The problem is that I want to hash the words to an index in the graph, but for that the endsize of the list needs to be known.
I start by adding a vector which will contain the entire wordlist, I use the size of this vector to set size of arraylist and then I iterate the vector to hash the words into the arraylist.
My adjacent list is of type:
ArrayList<LinkedList<String>> adj_list;
Here's how I use it:
public void adda(Vector<String> v){
M = v.size();
adj_list = new ArrayList<LinkedList<String>>(M);
for (int i = 0; i < M; i++){
add(v.get(i));
}
void add (String word){
int z = hash(word);
for (int i = z; i < M; i++){
if(adj_list.get(i)== null){
z=i;
adj_list.add(new LinkedList<String>());
break;
Hashfunction:
public static int hash(String key) {
int i;
int v = 0;
for (i = 0; i < key.length(); i++) {
v += key.charAt(i);
}
return v % M;
I have a strong feeling that just the idea of adding a vector to take the elements from it and add to an arraylist is stupid enough. I cannot come up with any better, working, ideas though (and the one I have right now isn't working either). Should I use an adjacency list at all? Is it a good idea to hash the words or are there any better ways? Does anyone sort of understand what type of program I am trying to create and have any idea that might be helpful?