### 题目

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.


Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0


Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

### DFS回溯算法

#### 代码

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(beginWord)) {
}
neighbours = findNeighbours(wordList);
minLen = null;
Set<String> path = new HashSet<String>();
backtracking(path, beginWord, endWord);
return (minLen == null)? 0 : minLen;
}
private Map<String, List<String>> neighbours;
private Integer minLen;
private Map<String, List<String>> findNeighbours(List<String> wordList) {
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < wordList.size(); i++) {
String a = wordList.get(i);
for (int j = i + 1; j < wordList.size(); j++) {
String b = wordList.get(j);
if (distance(a, b) == 1) {
if (!map.containsKey(a)) {
map.put(a, new ArrayList<String>());
}
if (!map.containsKey(b)) {
map.put(b, new ArrayList<String>());
}
}
}
}
return map;
}
// assetion: a.length() == b.length()
private int distance(String a, String b) {
int dis = 0;
for (int i = 0; i < a.length(); i++) {
if(a.charAt(i) != b.charAt(i)) {
dis++;
}
}
return dis;
}
private void backtracking(Set<String> path, String begin, String end) {
if (begin.equals(end)) {
minLen = (minLen == null)? path.size() : Math.min(minLen, path.size());
return;
}
if (neighbours.containsKey(begin)) {
for (String neighbour : neighbours.get(begin)) {
backtracking(path, neighbour, end);
path.remove(neighbour);
}
}
}
}
}


#### 代码

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
return bfs(beginWord, endWord, wordList);
}

private int bfs(String begin, String end, List<String> wordList) {
List<String> thisLevel = new ArrayList<>();
int level = 1;
while (!thisLevel.isEmpty()) {
List<String> nextLevel = new ArrayList<>();
for (String word : thisLevel) {
if (word.equals(end)) {
return level;
}
Iterator<String> ite = wordList.iterator();
while (ite.hasNext()) {
String anotherWord = ite.next();
if (distance(anotherWord, word) == 1) {
ite.remove();
}
}
}
thisLevel = nextLevel;
level++;
}
return 0;
}
// assetion: a.length() == b.length()
private int distance(String a, String b) {
int dis = 0;
for (int i = 0; i < a.length(); i++) {
if(a.charAt(i) != b.charAt(i)) {
dis++;
}
}
return dis;
}
}


### 优化的BFS

[hit] --> ["hot","dot","dog","lot","log","cog"]

"ait"
"bit"
"cit"
"dit"
...
...
"zit"
"hat"
"hbt"
"hct"
...
...



#### 代码

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
return bfs(beginWord, endWord, wordSet);
}
private int bfs(String begin, String end, Set<String> wordSet) {
List<String> thisLevel = new ArrayList<>();
int level = 1;
while (!thisLevel.isEmpty()) {
List<String> nextLevel = new ArrayList<>();
for (String word : thisLevel) {
if (word.equals(end)) {
return level;
}
char[] cs = word.toCharArray();
for (int i = 0; i < cs.length; i++) { // 枚举所有可能的相差要有一个字符的单词
char orig = cs[i];
for (char c = 'a' ; c <= 'z'; c++) {
if (c == orig) { continue; }
cs[i] = c;
String variant = new String(cs);
if (wordSet.remove(variant)) {
}
}
cs[i] = orig;
}
}
thisLevel = nextLevel;
level++;
}
return 0;
}
}