本文主要是介绍Crack LeetCode 之 127. Word Ladder，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/word-ladder/
本文的解釋部分來自於鏈接，出於學習目的我租了部分整理和修改：https://blog.csdn.net/linhuanmars/article/details/23029973
本題的本質是图，圖的顶点则是每个字符串。因為每次只能改一個字符，所以該字符串的每个字符可能对应的边有25个（26个小写字母减去自己），那么一个字符串可能存在的边是25*L条。接下来我們再检查这些边对应的字符串是否在字典里，以此類推就可以得到一个完整的图的结构。根据题目的要求，等价于求这个图一个顶点到另一个顶点的最短路径，我们用广度优先搜索即可。
該算法中最差情况是把所有长度为L的字符串都掃描一遍，或者把字典中的字符串都掃描一遍，而长度为L的字符串共有26^L，所以时间复杂度是O(min(26^L, size(dict))，空间上需要存储访问情况，也是O(min(26^L, size(dict))。C++代码如下：
class Solution
{
public:int ladderLength(string start, string end, vector<string>& wordList){if(start.empty() || end.empty() || start.length()!=end.length())return 0;list<string> strlist;set<string> visited;set<string> dic;int level= 1;int lastNum = 1;int curNum = 0;strlist.push_back(start);visited.insert(start);for (vector<string>::iterator ite = wordList.begin(); ite!=wordList.end(); ++ite)dic.insert(*ite);while(strlist.empty() == false) {string cur = strlist.front();strlist.pop_front();lastNum--;for(int i=0;i<cur.length();i++) {string charCur = cur;for(char c='a';c<='z';c++) {charCur[i] = c;if( dic.find(charCur)!=dic.end() && visited.find(charCur)==visited.end()) {if(charCur == end)return level+1;curNum++;strlist.push_back(charCur);visited.insert(charCur);}}}if(lastNum==0) {lastNum = curNum;curNum = 0;level++;}}return 0;}
};
Python代码如下：
class Solution:def ladderLength(self, beginWord, endWord, wordList):if not beginWord or not endWord or not wordList:return 0;wordSet = set()for word in wordList:wordSet.add(word)level = 1processedSet = set()curList = [beginWord]while True:level = level + 1nextList = []for curWord in curList:if curWord in processedSet:continuefor i in range(len(curWord)):part1 = curWord[:i]; part2 = curWord[i+1:]for j in 'abcdefghijklmnopqrstuvwxyz':nextword = part1 + j + part2if nextword == curWord:continueif nextword not in wordSet:continueif nextword == endWord:return levelnextList.append(nextword)processedSet.add(curWord)if not nextList:return 0curList = nextListreturn 0
这篇关于Crack LeetCode 之 127. Word Ladder的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
