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.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

其实看到这个题就有广搜的想法，刚做完 一道经典搜索题 ：http://blog.csdn.net/huruzun/article/details/39234511

下面是我AC java代码，没有经过太多优化，可以通过leetcode 。

public class Solution {    public int ladderLength(String start, String end, Set<String> dict) {    	if(start==null || end == null || start.equals(end) || start.length()!=end.length()){    		return 0;    	}    	Queue<String> queue = new LinkedList<String>();        queue.offer(start);        Map<String, Integer> DictMap = new HashMap<String, Integer>();        DictMap.put(start, 1);        // 利用广搜，start 字符串从头到尾每个字符进行更换。        while(!queue.isEmpty()){        	String interString = queue.poll();        	int TrasformTimes = DictMap.get(interString);        	        	for(int i=0;i<interString.length();i++){        		for(char c='a';c<='z';c++){        			if(interString.charAt(i)==c){        				continue;        			}        			StringBuilder sb = new StringBuilder(interString);        			sb.setCharAt(i, c);        			if(sb.toString().equals(end)){        				return TrasformTimes+1;        			}        			// 如果字典里有，并且先前没有出现        			if(dict.contains(sb.toString())&& !DictMap.containsKey(sb.toString())){        				queue.add(sb.toString());        				DictMap.put(sb.toString(), TrasformTimes+1);        			}        		}        	}        }        return 0;    }}

各位有更好思路请赐教，感谢。

Word Ladder