LeetCode-127. Word Ladder

LeetCode-127. Word Ladder

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:

Only one letter can be changed at a time.Each transformed word must exist in the word list. Note thatbeginWordisnota transformed word.

Note:

Return 0 if there is no such transformation sequence.All words have the same length.All words contain only lowercase alphabetic characters.You may assume no duplicates in the word list.You may assumebeginWordandendWordare non-empty and are not the same.

Example 1:

Input:beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]Output: 5Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",return its length 5.

Example 2:

Input:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]Output: 0Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

题解：

很经典的广度优先搜索。

一个pair队列保存当前状态和步长，按字母表搜索每个位置，找出每种wordList中有的可能，再放进队列中，逐一找到目标值。

class Solution {public: int ladderLength(string beginWord, string endWord, vector& wordList) { int res = INT_MAX, len = beginWord.length(); queue> q; unordered_set words(wordList.begin(), wordList.end()); unordered_set visit; q.push({beginWord, 1}); visit.insert(beginWord); while (q.empty() == false) { auto cur = q.front(); q.pop(); if (cur.first == endWord) { res = min(res, cur.second); continue; } if (cur.second >= res) { continue; } for (int i = 0; i < len; i++) { string tmp = cur.first; for (int j = 0; j < 26; j++) { tmp[i] = 'a' + j; if (words.find(tmp) != words.end() && visit.find(tmp) == visit.end()) { q.push({tmp, cur.second + 1}); visit.insert(tmp); } } } } if (res == INT_MAX) { return 0; } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。