Word ladder help

[AdrianV]

Hello,

I was asked to write a word ladder game (Not really a game, just the user input two words and the computer prints the word ladder) but I am having a lot of problems thinking of how I could implement it. I am required to implement and use a graph data structure for the project, and I can use any other data structure(Stack, Queue, Tree, Doubly Linked list, ect;) by using a C++ library (I am only required to implement the graph myself, I can use any other data structure if I want to by using a library) but I can't seem to figure out the basic concept on how to implement it... I don't know what data structures to use, and I kinda see how a graph is useful in this situation but I can't visualize how I would use it. I don't want anyone to write code for me, I was just wondering if any of you guys could help me figure out how or where I can implement the word ladder or what data structures I could use. I just need some logical and conceptual help. I will really appreciate ANY help! Thank you for your time!!!

[ne555]

You could have just bumped, you made me lose the bookmarks.


http://en.wikipedia.org/wiki/Breadth-first_search will give you the shortest path to pass from one word to the other.

To implement the graph you may store in each node a list of neighbours. Would recommend to use the position of the other element.
Or you could use a adjacency matrix, If there is an edge then m[K][L] would be set.

You'll need to perform an analysis of memory consumption and time complexity, to know if this solution is viable.

There is also the issue of creating the graph. If the number of words is considerable, checking each one to know if it could be a neighbour it would be quite slow.
You could try a trie and search for the word with one wildcard character. Or use a tree instead, and search with lower_bound/upper_bound