直接层序遍历，结果有部分测试样例超时；
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { //利用二叉树的层序遍历； if(beginWord.size()!=endWord.size()) return 0; unordered_map<string,int> h; for(int i=0;i<wordList.size();i++){ h[wordList[i]]=1; } if(h[endWord]==0) return 0; int level=1; queue<string> q; q.push(beginWord); while(!q.empty()){ level++; int qlen=q.size(); while(qlen--){ string front=q.front(); //cout<<front<<","; q.pop(); for(int i=0;i<wordList.size();i++){ if(h[wordList[i]]==0) continue; if(dis(front,wordList[i])==1){ if(wordList[i]==endWord) return level; q.push(wordList[i]); h[wordList[i]]=0; } } } //cout<<endl; } return 0; } int dis(string w1,string w2){ if(w1.size()!=w2.size()) return 0; int res=0; for(int i=0;i<w1.size();i++){ res+=(w1[i]-w2[i]==0)?0:1; if(res>1) return res; } return res; } };
究其原因，是因为距离计算每次都要调用函数过于复杂，由于两两单词间计算距离，并且计算距离时又需要对每个字母进行遍历，因此timeO(n^2*m)
改变距离的计算，对其做预处理，列出每个单词的状态，比如hog 可列为 *og,h*g,ho*；通过临接表来表示，即一个键值（key）为状态，值（value）为hog，即unordered_map<string,set<string>> m(单词状态，单词列表) 对n个词，每个词m个状态进行检索， time O(mn)级别，
C++代码如下：
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { //利用二叉树的层序遍历； if(beginWord.size()!=endWord.size()) return 0; unordered_map<string,int> h; for(int i=0;i<wordList.size();i++){ h[wordList[i]]=1; } if(h[endWord]==0) return 0; int level=1; queue<string> q; q.push(beginWord); while(!q.empty()){ level++; int qlen=q.size(); while(qlen--){ string front=q.front(); //cout<<front<<","; q.pop(); for(int i=0;i<wordList.size();i++){ if(h[wordList[i]]==0) continue; if(dis(front,wordList[i])==1){ if(wordList[i]==endWord) return level; q.push(wordList[i]); h[wordList[i]]=0; } } } //cout<<endl; } return 0; } int dis(string w1,string w2){ if(w1.size()!=w2.size()) return 0; int res=0; for(int i=0;i<w1.size();i++){ res+=(w1[i]-w2[i]==0)?0:1; if(res>1) return res; } return res; } };
原文：https://www.cnblogs.com/joelwang/p/11053278.html