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.

Tips and Divergent thinking:

N/A

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on May 1, 2013