I want to turn one string into another with only single letter substitions.  What is a good way to do this, passing through only valid words in between (this website has some examples)?Valid here means a word in English as this is the domain I consider.My current idea is that I could use a shortest path algorithm with the Hamming distance for edge weights. The problem is that it will take a long time to build the graph, and even then the weight is not so precise in terms of distance (though it will never underestimate it) unless the weight is one, so I would probably have to find a to build a graph that only had weights of one.What would be the easiest way to build the graph? Am I taking entirely the wrong approach?
Turn one string into another with single letter substitions
algorithms;strings;string metrics