首页 > 代码库 > Leetcode: Word Ladder
Leetcode: Word Ladder
题目:
https://oj.leetcode.com/problems/word-ladder/
分析:
1. 求最短路径, 用BFS算法。 [3]
2. 求各个单词之间的邻接关系, 不能用邻接矩阵, 否则会Time Limit Exceeded。 [2]
因为并非所有单词之间的邻接关系在求解过程中都需要, 只需要求解用到的一些单词的邻居即可。要是求邻接矩阵的话, 会花费大量时间。
3. 一个单词访问过了之后, 直接从dict中删除即可, 从而避免重复加入队列,进而导致浪费时间。[1]
4. 关于如何记录路径长, 可以再创建一个depth队列, 这样que队列push时, depth队列也同时的push一个对应的路径。[1]
代码:
class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { dict.insert(end); queue<string> que; queue<int> depth; que.push(start); depth.push(2); int len; while (!que.empty()) { string ver = que.front(); que.pop(); len = depth.front(); depth.pop(); vector<string> res; adjacency(ver, dict, res); for (auto &r : res) { if (r == end) return len; else { dict.erase(r); que.push(r); depth.push(len+1); } } } return 0; }; void adjacency(const string &ver, const unordered_set<string> &dict, vector<string> &res) { for (int i = 0; i < ver.size(); i++) { string temp = ver; for (int j = 'a'; j <= 'z'; j++) { temp[i] = j; if (temp != ver && dict.find(temp) != dict.end()) res.push_back(temp); } } return; } };
参考:
[1] http://blog.csdn.net/lanxu_yy/article/details/17588317
[2] http://blog.csdn.net/yutianzuijin/article/details/12887747
[3] 《数据结构(C++语言版)》(第三版) 邓俊辉 p169
Leetcode: Word Ladder
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。