String transformation

Question

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!

possible duplicate of [Shortest path to transform one word into another](http://stackoverflow.com/questions/1521958/shortest-path-to-transform-one-word-into-another) — NPE, Oct 11 '11 at 17:07
ah, thanks aix. do you agree with that answer, though, that a* is the best choice? — OckhamsRazor, Oct 11 '11 at 17:14

score 1 · Accepted Answer · edited May 23 '17 at 11:47

1

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.

edited May 23 '17 at 11:47

Community

1
1

answered Oct 11 '11 at 17:20

Ilmari Karonen

49,047
9
93
153

score 0 · Answer 2 · answered Oct 11 '11 at 17:08

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.

String transformation

2 Answers2

Linked