LeetCode *** 127. Word Ladder（BFS）

本文主要是介绍LeetCode *** 127. Word Ladder（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

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

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

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

分析：

代码：

class Solution {
public:int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {if (wordList.empty())return 0;vector<string> wordlist(wordList.begin(), wordList.end());int len = wordlist[0].size();queue<string> que;queue<int> qur;vector<string>::iterator it;que.push(beginWord);qur.push(1);while (!que.empty()) {string key = que.front();int level = qur.front();qur.pop();que.pop();int rec = 0;for (int i = 0; i<len&&rec<2; ++i)if (key[i] != endWord[i])rec++;if (rec<2)return level + 1;it = wordlist.begin();while (it != wordlist.end()) {rec = 0;for (int i = 0; i<len&&rec<2; ++i)if (key[i] != (*it)[i])rec++;if (rec == 1) {que.push(*it);qur.push(level + 1);it = wordlist.erase(it);}else it++;}}return 0;}
};

这篇关于LeetCode *** 127. Word Ladder（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---