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

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

Solution: each word in the dictionary, as well as the start and the end word can be seen as nodes of a graph. There is an edge between two words, if their difference is just one letter. Therefore, the question becomes to construct a graph first, then you can find whether there is a path between the start and end nodes. See the following illustration. Either a BFS or DFS traversal will work.

"hit" --- "hot"-------"dot"
             |             |
           "lot"       "dog"
              \          /   |
              "log" -----"cog"

Java语言: WordLadder

01 public int ladderLength(String start, String end, HashSet<String> dict) {
02     LinkedList<String> queue=new LinkedList<String>();
03     LinkedList<Integer> steps=new LinkedList<Integer>();
04     HashSet<String> visited=new HashSet<String>();
05     queue.add(start);
06     steps.add(1);
07     //This hashtable is used to find neighbors of a given node
08     Hashtable<String, ArrayList<String>> neighborTable=new Hashtable<String, ArrayList<String>>();
09   
10     neighborTable.put(start, new ArrayList<String>());
11     for(String s: dict)
12     {
13         neighborTable.put(s, new ArrayList<String>());
14     }
15     neighborTable.put(end, new ArrayList<String>());
16     //Construct the graph
17     generateGraph(start,end,dict,neighborTable);      
18     while(queue.size()!=0)
19     {
20         String top=queue.remove();
21         int length=steps.remove();
22         ArrayList<String> neighbors=findNeighbors(top,neighborTable);
23         if(neighbors.size()!=0)
24         {
25             for(String s:neighbors)
26             {
27                 if(!visited.contains(s))
28                 {
29                     if(s.equals(end))
30                     {
31                         return length+1;
32                     }
33                     queue.add(s);    
34                     steps.add(length+1);
35                 }
36             }
37             length++;
38         }
39     }
40     return 0;
41 }
42 
43 public void generateGraph(String start, String end, HashSet<String> dict, Hashtable<String, ArrayList<String>> neighborTable)
44 {
45     for(String u:neighborTable.keySet())
46     {
47         ArrayList<String> adj_u=neighborTable.get(u);
48         for(String v:neighborTable.keySet() )
49         {
50             ArrayList<String> adj_v=neighborTable.get(v);
51             if(getDiff(u,v)==1)
52             {
53                 if(!adj_u.contains(v))
54                 {
55                     adj_u.add(v);
56                 }
57                 if(!adj_v.contains(u))
58                 {
59                     adj_v.add(u);
60                 }
61             }
62             neighborTable.put(v, adj_v);              
63         }
64         neighborTable.put(u,adj_u);
65     }
66 }
67 
68 public ArrayList<String> findNeighbors(String word, Hashtable<String,ArrayList<String>>neighborTable)
69 {
70     return neighborTable.get(word);
71 }
72 
73 public int getDiff(String word1, String word2)
74 {
75     if(word1.equals(word2))
76         return 0;
77     int diff=0;      
78     for(int i=0;i<word1.length();i++)
79     {
80         if(word1.charAt(i)!=word2.charAt(i))
81         {
82             diff++;
83         }
84     }
85     return diff;
86 }