题目：
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 beginWordis 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.
分析：
给定起始和终止两个单词，和一个单词列表，要求我们使用列表中的单词将起始和终止单词连接起来，连接的规则是要求每次只改变一个字符，且在列表中存在，终止单词也需要在列表中。
我们可以利用广度优先搜索，从起始单词开始，将每一位字符从a到z依次改变，如果改变后的单词在列表中，就记录下来，并在集合中删去，这样做的目的是为了防止重复的搜索，例如dog-dop-dog，这样是浪费时间的，当新加入的单词和最终单词相同时，返回步骤数即可，如果保存搜索单词的集合(队列)为空时，证明已经搜索结束，且没有找到，返回0即可。
还可以利用双向广度优先搜索进行优化，思想就是同时从起始单词和终止单词开始搜索，也是通过改变字符，且在单词列表中便加入到两个搜索集中，当一侧搜索出来的单词，在另一侧的搜索单词集中，意味着出现了解。至于搜索的次序，如果当一方的集合中的单词数量小于另一方时，就优先从数量小的集合开始搜索。
程序：
C++
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
//set<string> dict;
unordered_set<string> dict;
for(string s:wordList)
dict.insert(s);
if(dict.count(endWord) == )
return ;
queue<string> q;
q.push(beginWord);
int l = beginWord.length();
int step = ;
while(!q.empty()){
step++;
int len = q.size();
for(int i = ; i < len; ++i){
string word = q.front();
q.pop();
for(int j = ; j < l; ++j){
char ch = word[j];
for(int k = 'a'; k <= 'z'; ++k){
if(k == ch)
continue;
word[j] = k;
if(word == endWord)
return step+;
if(dict.count(word) == )
continue;
q.push(word);
dict.erase(word);
}
word[j] = ch;
}
}
}
return ;
}
};
//Bidirectional BFS
//Runtime: 28 ms, faster than 98.16% of C++ online submissions for Word Ladder.
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
//set<string> dict;
unordered_set<string> dict;
for(string s:wordList)
dict.insert(s);
if(dict.count(endWord) == )
return ;
unordered_set<string> q1;
unordered_set<string> q2;
q1.insert(beginWord);
q2.insert(endWord);
int l = beginWord.length();
int step = ;
while(!q1.empty() && !q2.empty()){
step++;
if(q1.size() > q2.size())
swap(q1, q2);
unordered_set<string> q;
for(string word:q1){
for(int j = ; j < l; ++j){
char ch = word[j];
for(int k = 'a'; k <= 'z'; ++k){
if(k == ch)
continue;
word[j] = k;
if(q2.count(word))
return step+;
if(dict.count(word) == )
continue;
q.insert(word);
dict.erase(word);
}
word[j] = ch;
}
}
swap(q, q1);
}
return ;
}
};
Java
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if(!dict.contains(endWord))
return 0;
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
int l = beginWord.length();
int step = 0;
while(!q.isEmpty()){
step++;
int len = q.size();
for(int i = 0; i < len; ++i){
//String word = q.poll();
StringBuilder word = new StringBuilder(q.poll());
for(int j = 0; j < l; ++j){
char ch = word.charAt(j);
for(int k = 'a'; k < 'z'; ++k){
if(ch == k)
continue;
word.setCharAt(j, (char)k);
String w = word.toString();
if(w.equals(endWord))
return step+1;
if(!dict.contains(w))
continue;
q.offer(w);
dict.remove(w);
}
word.setCharAt(j, ch);
}
}
}
return 0;
}
}
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if(!dict.contains(endWord))
return 0;
Set<String> q1 = new HashSet<>();
q1.add(beginWord);
Set<String> q2 = new HashSet<>();
q2.add(endWord);
int l = beginWord.length();
int step = 0;
while(!q1.isEmpty() && !q2.isEmpty()){
step++;
if(q1.size() > q2.size()){
Set<String> temp = q1;
q1 = q2;
q2 = temp;
}
Set<String> q = new HashSet<>();
for(String s:q1){
StringBuilder str = new StringBuilder(s);
for(int i = 0; i < l; ++i){
char ch = str.charAt(i);
for(int j = 'a'; j <= 'z'; ++j){
if(ch == j)
continue;
str.setCharAt(i, (char)j);
String word = str.toString();
if (q2.contains(word))
return step + 1;
if(!dict.contains(word))
continue;
dict.remove(word);
q.add(word);
}
str.setCharAt(i, ch);
}
}
q1.clear();
q1.addAll(q);
}
return 0;
}
}