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$

2 Answers 2

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$
0
$\begingroup$

The BFS algorithm still works with some changes. You'd basically have to pad an extra character in all the places. For instance, if there's no word of the same length to move from the word "hot", you check for words of length 4 characters. For this, you'd have to check all 26 characters in 4 positions. [x]hot, h[x]ot, ho[x]t, hot[x]

Check for the presence of the words from these transformations and add them to your queue. You'd basically have to do this for all lengths between beginWord.length and endWord.length

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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