leetcode: Word Ladder II

Problem Description:

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

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

Return

[
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

 

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution and Precautions:

Essentially, this could be solved by using BFS, now each node have three status: discovered, undiscovered, processed, for those discovered (but not processed nodes), we need to test whether the distance is equal to the distance of the current node (popped out node by BFS) plus 1, if it is equal, then this current node should be added into the discovered node’s parent list. After BFS, one could use DFS from the end to the start, to print all the paths.

Written on May 1, 2013