Given two words (start and end), and a dictionary of words, find the length of shortest sequences of words from start to end, such that at each step only one letter is changed.

e.g: start word: hat stop word: dog

dictionary{cat, dot, cot, fat}

sequence: hat->cat->cot->dot->dog

## Solution

• 和当前单词相邻的单词是：对当前单词改变一个字母且在字典中存在的单词
• 找到一个单词的相邻单词，加入bfs队列后，要从字典中删除，因为不删除的话会造成类似于hog->hot->hog的死循环。而删除对求最短路径没有影响，因为我们第一次找到该单词肯定是最短路径，即使后面其他单词也可能转化得到它，路径肯定不会比当前的路径短（如果要输出所有最短路径，则不能立即从字典中删除，具体见下一题）
• bfs队列中用NULL来标识层与层的间隔，每次碰到层的结尾，遍历深度+1

## Code

``````int wordlength(String word, ArrayList<String> dict){
int step = 1;
Queue<String> queue = new Queue<String>();
HashSet<String> hashset = new HashSet<String>();

while (!queue.isEmpty()){
String tmp = queue.poll();
if (tmp.equals(word)){
return step;
}
if (tmp == null !&& queue.isEmpty(){
step++;
} else if (!queue.isEmpty()){
for (int i = 0; i < tmp.length(); i++){
for (int j = 'a'; j < 'z'; j++){
String mid = tmp.substring(0,i) + (char)j + tmp.substring(i+1);
if (!hashset.contains(mid) && dict.contains(mid)){