Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- 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.
1 public class Solution { 2 public int ladderLength(String start, String end, HashSet<String> dict) { 3 if(dict.size()==0) 4 return 0; 5 Queue<String> queue = new LinkedList<String> (); 6 Queue<Integer> len = new LinkedList<Integer> (); 7 dict.add(start); 8 dict.add(end); 9 queue.offer(start); 10 len.offer(1); 11 while(!queue.isEmpty()){ 12 String s = queue.poll(); 13 int l = len.poll(); 14 if(s.equals(end)) return l; 15 for(int i=0;i<s.length();i++){ 16 char[] chars = s.toCharArray(); 17 for(char c=‘a‘;c<=‘z‘;c++){ 18 if(c!=chars[i]){ 19 chars[i]=c; 20 String temp = new String(chars); 21 if(dict.contains(temp)){ 22 len.offer(l+1); 23 queue.offer(temp); 24 dict.remove(temp); 25 } 26 } 27 } 28 } 29 } 30 return 0; 31 } 32 }