Daily Archives: November 5, 2015

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary. For example, given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

This is a dijistra problem which can build graph, and run dijistra on it. It be solved in O(n^2) time. Dijistra is actually a BFS.

Check my code on github: link