Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example,
Given: start ="hit" end ="cog" dict =["hot","dot","dog","lot","log"]
As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length5.
Note:
Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.
C++
class Solution { bool diff(string a,string b){ int c=0; for(int i=0;i<a.size();i++) if(a[i]!=b[i]) c++; if(c==1) return true; return false; } public: int ladderLength(string start,string end,unordered_set<string> &dict){ dict.insert(end); dict.erase(start); queue<string> q; q.push(start); int length=0; while(q.size()>0){ length++; int QueueLength=q.size(); for(int i=0;i<QueueLength;i++){ start=q.front(); q.pop(); if(start==end) return length; for(unordered_set<string >::iterator iter=dict.begin();iter!= dict.end();){ if(diff(start,*iter)){ q.push(*iter); dict.erase(iter++); }else iter++; } } } return 0; } int ladderLength2(string start, string ends, unordered_set<string> &dict) { int res=1; queue<string> q; q.push(start); while(!q.empty()){ int size=q.size(); while(size>0){ string top=q.front(); q.pop(); size--; if(diff(top,ends)) return res+1; for(unordered_set<string >::iterator i =dict.begin();i!=dict.end();){ if(diff(*i,top)){ q.push(*i); dict.erase(i++); }else i++; } } res++; } return 0; } };
转载于:https://www.cnblogs.com/vercont/p/10210235.html
相关资源：JAVA上百实例源码以及开源项目