【算法刷题】leetcodeword ladder

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 timeEach 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.

使用BFS搜索，即可以将dict分成若干层，每一层间的单词都与上一层相关的单词相差一个字符，从start开始匹配第一层，使用队列进行BFS，每次加入队列，就把单词从dict里删除，同时，要注意每一层的个数情况，进行while循环，并计数层数

int ladderLength(string start, string end, unordered_set<string> &dict) { queue<string> strqueue; int res = 1; strqueue.push(start); while (!strqueue.empty()) { int len = strqueue.size(); while (len>0) { string frontstr = strqueue.front(); strqueue.pop(); len--; if (isDifOne(frontstr, end)) return res+1; //BFS一轮，加了一层 auto enditer = dict.end(); for (auto iter = dict.begin(); iter != enditer;) {//此处要注意关联容器的删除，会影响迭代器，使迭代器失效 if (isDifOne(frontstr, *iter)) { strqueue.push(*iter); dict.erase(iter++); } else { ++iter; } } } ++res; } return 0; } bool isDifOne(string l, string r) { int sum(0); int length = l.length(); for (int i = 0; i < length; ++i) { if (l[i] != r[i]) ++sum; } return sum == 1 ? true : false; }