Brainstorming word path

[Skynet]

I have this problem that I need to solve. Here is the link.

http://faculty.utpa.edu/rtschweller/CS3333/CS3333S2013/hwk/wordConnect.htm

I have to design something to search words according to that and I think I can do it but the problem I am having is how would I go about doing this? I think I can design something that would link the words together based on the changes in letters but I'm not sure how exactly I would do that. I wanted to brainstorm and see what you all thought and maybe see if anyone could come up with any better ideas than I.

I have an idea that maybe I can get all the words and sort them into bins based on how many letters they have. One bin will be strictly for words with three letters, another will be strictly for words with four letters and so on and so forth. From those bins I can maybe make a vertex where it will look through the bins and find a word that changes by one letter and such till I get to the other word but at the same time I'm not sure how to implement that.

Any ideas?

[tfityo]

You should consider only 3,4, and 5 letter words. So you can do it by brute-force:
for each 3-letter word build try every one-letter substitution and check if a new word is in the dictionary. If it is connect these words. For an instance:
You are checking rat:
1) try to change the first letter:
aat - not in the dictionary
bat - in; connect bat and rat
cat - in; connect cat and rat
dat - not;
...
2) try to change the second letter
...
The complexity is 26^3*(number of 3-letter words) - feasible.

Or you can make a double-loop and check every pair of words if they differ only in 1 letter; complexity will be (number of 3-letter words)^2 - still feasible.

[Skynet]

That is one thing I was considering but at the same time I didn't know if that was feasible or not. I want to sort them into the bins but I'm not sure how to tell it to differ the words from 3,4,or 5 letter words. As a matter of fact, I'm not entirely sure how I would sort the words themselves. All I truly know is something like cat and rat could sort with cat being first if you were to put them into any which way here. --> if(string a < string b) then switch and such but as for the arrays, I want to make 26 bins per array, bin a, bin b, bin c, etc.... with all three letter a words in bin a, all three letter b words in bin b, etc.... I could do this with numbers no problem but not sure how to go about this with words

[tfityo]

The total number of words in English is about 100,000. 3,4 or 5-letter words should be considerably less (you also have dictionary file, you can find exact numbers). 10^9 operations is feasible amount on modern computer. (100,000)^2 - will be slow, but still in range of couple of minutes.

I don't understand why you need to put letters in bins. You need to to build a graph, where two words are connected if only one letter change transforms one to the other.

[ne555]

Try a trie.

[Skynet]

What exactly is a trie? I tried looking it up but I couldn't really grasp the concept. I'm sorry

[ne555]

You've got a tree, but each node holds only 1 letter.
If you go from the root to a node you form a word, as you can see in
http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/400px-Trie_example.svg.png

So it follows the common prefix, and branch when the string start to differ.

A possible implementation

class trie{
   class node{
      node* son['z'-'a'+1];
      bool terminal; //I'm not just a prefix, but a word
   };
   node root;
};

Try to figure out a way to search if a word is in the trie.