Algorithm for Converting one word to other word by changing each letter per iteration which should form an another meaningful word?

Question

I want to make an algorithm for changing one word to other. For example the given word is "MUD" and I need to convert it to "BED". For each iteration I can change one character, but that should form an another meaningful word. For example "MUD" can be change as "MAD". Like this I need to find the shortest path to convert the "MUD" to "BED".

A separate method is provided for finding the valid word. IsWord() is a method which will give us the boolean result whether the given string is valid or not. So dont need to worry about that.

I also dont need to worry about efficiency or lines of code , etc. Do any one have any idea how to make this algorithm. If so please help me.

Thanks in Advance.

(I know that we have to use tree and have to do binary traversal, but I have no idea how to use it in this algorithm)

Answer 1

This is called a word ladder. Check out the post The Longest Word Ladder Puzzle Ever on Wolfram Blog.

Answer 2

You start by having a sorted queue with elements (strings). Each element has a rating/distance (according to an heuristic) to the target word. This can be a Hamming Distance. And the sorted queue uses this distance to push on top the word closest to the target.

You take your first word, add it to the queue. Extract from the queue the first element, expand all of its children (words that can be obtained from it through a single conversion) and put them in the queue. Do this until the element you get from the queue is the one you are searching for or the queue is empty.

Answer 3

Create a graph the following way:

Each word is a node and two nodes are connected if you can go from one word to another in one step.

Now find the shortest distance and path between original word and final word.

See: http://en.wikipedia.org/wiki/Shortest_path_problem on how to calculate shortest path.

Answer 4

In each iteration, make all possible new words form the words you have and collect them in a list, set or whatever. Filter out duplicates and words you already had before. For example:

1. (BED)
2. (BAD, BET, ....)
3. (MAD, BAN, ...., BUT, BOT, ....)

You either end up with an empty list, then the problem is not solvable, or the sought word is in the list.