String transformation

I came across the following article which got me interested in this particular problem.

Given two words "CAT", "FAR" determine if you can get from the first to the second via single transformations of valid words....e.g. 1 transformation gets you from CAT to CAR changing T to R, then another gets you from CAR to FAR changing the C to F...all are valid english words.

Any ideas? Not really sure how to begin to be honest. If you point me in the right direction, then that will be enough.开发者_开发技巧 Thanks!

As noted in this answer (thanks, aix), this is a shortest-path problem, and can be efficiently solved with the A* algorithm using the Hamming distance (i.e. the number of letters by which two words differ) as a heuristic.

There are 3 points to consider :

1 How many characters are different between the two given words ? Its just not the char, but its position in the word also matters. So compare on position.

2 Determine for each transformation , if the resulting word is a valid english word. Some reference of correct words will be needed here.

3 Work out the sequence of transforms that each intermediate word is valid.

This is going to be a try-err approach I guess. Any backtracking algorithm will be a good choice.