首页 > 代码库 > Word Ladder

Word Ladder

该题目考察的知识点是宽度优先搜索,宽度优先搜索可以用队列保存计算的中间变量。需要注意的是urordered_set,是哈希表实现,查找的效率很高。利用这个特点做题。

具体实现的代码如下:

class Solution {public:	unordered_set<string> data;	queue<pair<string,int>> result;    int ladderLength(string start, string end, unordered_set<string> &dict) {	  pair<string,int> temp;      temp.second = 1;	  temp.first  = start;      if(CheckResult(start,end) == true)	  	return 2;      GetData(temp,dict);	  if(result.size() == 0)	  	return 0;	      while(result.size() !=0)      {         temp = result.front();		 if(CheckResult(temp.first, end)== true)		 {            return temp.second+1;		 }		 result.pop();		 GetData(temp,dict);		 	 	  }     return 0;		            }	bool GetData(pair<string,int> &start,unordered_set<string> &dict)	{	    int i=0,j=0;		string temp;		pair<string,int> pattern;	        for(i = 0; i < start.first.size(); i++)        {           temp = start.first;           for(j=0; j< 26;j++)           {             temp[i] = ‘a‘+j;			 if(dict.find(temp) != dict.end())			 {			    pattern.first   = temp;				pattern.second  = start.second + 1;                result.push(pattern);				dict.erase(temp);			 }		   }		}		return true;        	}	   bool CheckResult(string &temp, string &end)   {      int i=0;	  int count =0;	  for(i=0; i< temp.size();i++)	  {         if(temp[i] != end[i])         {            count++;		 }	  }      if(count == 1)	   return true;	  else	   return false;   }};

 

Word Ladder