## Question

### Problem Statement

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.

## 题解

1. start 和 end 相等。
2. end 在 dict 中，且 start 可以转换为 dict 中的一个单词。
3. end 不在 dict 中，但可由 start 或者 dict 中的一个单词转化而来。
4. end 无法由 start 转化而来。

### Java

public class Solution {
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return an integer
*/
public int ladderLength(String start, String end, Set<String> dict) {
if (start == null && end == null) return 0;
if (start.length() == 0 && end.length() == 0) return 0;
assert(start.length() == end.length());
if (dict == null || dict.size() == 0) {
return 0;
}

Set<String> hash = new HashSet<String>();
q.offer(start);
while (!q.isEmpty()) {
int qLen = q.size();
for (int i = 0; i < qLen; i++) {
String strTemp = q.poll();

for (String nextWord : getNextWords(strTemp, dict)) {
// filter visited word in the dict
if (hash.contains(nextWord)) continue;
q.offer(nextWord);
}
}
}

return 0;
}

private Set<String> getNextWords(String curr, Set<String> dict) {
Set<String> nextWords = new HashSet<String>();
for (int i = 0; i < curr.length(); i++) {
char[] chars = curr.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String temp = new String(chars);
if (dict.contains(temp)) {
}
}
}

return nextWords;
}
}


### 源码分析

#### BFS 和哈希表的配合使用

BFS 用作搜索，哈希表用于记录已经访问节点。在可以改变输入数据的前提下，需要将 end 加入 dict 中，否则对于不在 dict 中出现的 end 会有问题。