[leetcode] 127. Word Ladder

[leetcode] 127. Word Ladder

Description

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 that beginWord is not a 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 assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:

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

Output:

5

Explanation:

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:

0

Explanation:

The endWord "cog" is not in wordList, therefore no possible transformation.

分析

题目的意思是：给定开始单词和结束单词，还有一个单词词典，求从开始单词到结束单词的最小路径。

本题用了一个队列，先把start放进去，然后每次从队列里面取字符串，计算字符串与词典之间的距离，如果距离为1，我们就把字符串加入队列，然后长度+1，这样一直遍历到队列为空为止。

代码

class Solution {public: int ladderLength(string beginWord, string endWord, vector& wordList) { unordered_set dict(wordList.begin(),wordList.end()); unordered_map m; queue q; m[beginWord]=1; q.push(beginWord); while(!q.empty()){ string word=q.front(); q.pop(); for(int i=0;i

参考文献

​​[编程题]word-ladder​​​​[LeetCode] Word Ladder 词语阶梯​​

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