leetcode: Word Ladder I

Problem Description:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

A1s one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution and Precautions:

This problem could be solve by BFS from the start to the end, once the end is found, just return the distance from the end to the start. It is a standard BFS problem. Several issues need to be addressed before successfully solving this problem by BFS:

(1) Instead of building the graph explicitly, one should perform the search on the fly by testing each possible neighbor of a word (by chaning each character in that word, there is 25 * word.size() number of different neightbors), whether this neighbor is in the given dictionary

(2) The start and end word might be be not in the dictionary, always insert the start and end word into the given dictionary before heading into BFS

Tips and Divergent thinking:

N/A

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


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

Written on May 1, 2013