1
$\begingroup$

Is there some one who know any algorithm for word ladder problem with words of different length?

Actually we have some strings with same length and some strings with one length longer but not from any size(any size means: one string with size 10 and one string with size 1000).

any link or advise is acceptable.

my solution is this: build a graph with strings in the nodes and nodes are connected if their strings can be converted to each other just by changing one letter, then using BFS.

word ladder problem

$\endgroup$
1
$\begingroup$

Your algorithm that runs breadth-first search (BFS) on the graph built with words as nodes and pairs of words that differ by one letter as edges is the natural algorithm to solve the problem, whether the words are different lengths or not.

I would just call call your algorithm as a BFS algorithm. It is classic application of BFS to search for the shortest paths between two nodes of a graph where the length of a path is simply the number of its edges.

If we let the BFS algorithm run until all nodes has been visited, then it will be able to find all shortest paths between a source node and all other nodes.

You can find some detailed comparison between BFS and Dijkstra algorithm for shortest path in a graph here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.