Given list of word in dictionary, how to find minimum of steps to change a given word to another?

Question

Given {cap, cat, mat, map}
Input: cap, mat

Number of Steps: 2

Answer 1

You can model it as a graph problem where words will be nodes of the graph and two
nodes are connected if and only if they are of same length and differ in one char.

You can preprocess the dictionary and create this graph, an example of such processing is -

fix cap stack
| | |
six cat smack
|
mat
|
map

Then you can have a mapping from the word to the nodes of graph representing the word, which can be done using map (or HashMap in Java).

Once you have the above mapping in place, all you have to do is see if there exists a path between the two graph nodes, which can easily be done using BFS and you can also calculate the min distance also using BFS.

For more infoclick here