Word Ladder

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

Example

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

As 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.

 

用BFS做，字符串只相差一个字符的就当作有边。

1 public class Solution { 2     /** 3       * @param start, a string 4       * @param end, a string 5       * @param dict, a set of string 6       * @return an integer 7       */ 8     public int ladderLength(String start, String end, Set
       
         dict) { 9         Queue q = new LinkedList();10         dict.add(end);11         int reslut = 0;12         13         //转成List方便标记,其实也可以将搜索过的String从Set中移除14         List
        
          list = new ArrayList
         
          (dict);15         int[] flag = new int[list.size()];16         q.add(start);17         int n = 1;18         int x = 0;19         while(q.size() > 0) {20             String y = (String)q.remove();21             n--;22             for (int i = 0;i