首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。