本文共 1458 字,大约阅读时间需要 4 分钟。
给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:
说明:
示例 1:
输入:beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]输出: 5解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2:
输入:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]输出: 0解释: endWord "cog" 不在字典中,所以无法进行转换。
想了个最简单的方法,想着可能超时,结果没超时。。。但是复杂度很高。。。
原因出现在字符串查找是否入队上和vector选种元素的删除上。
附上第一次写的代码:
C++:class Solution {public: struct node { int num; string s; }; int ladderLength(string beginWord, string endWord, vector& wordList) { queue q; int Size=wordList.size(); int vis[Size+1]; memset (vis,0,sizeof(vis)); node now,next; now.num=1; now.s=beginWord; q.push(now); while (!q.empty()) { now=q.front(); q.pop(); if(now.s==endWord) return now.num; for (int i=0;i
看了别人的代码, 恍然大悟。。 。
然后模仿大佬的代码写了一个, 发现果然快了好多。 。
代码如下:
class Solution {public: int ladderLength(string beginWord, string endWord, vector& wordList) { queue q; map m1; //储存vector中的字符串便于查找是否存在 map re; //储存结果 int Size=wordList.size(); for (int i=0;i
转载地址:http://avaen.baihongyu.com/