首页 > 代码库 > 18. Word Ladder && Word Ladder II
18. Word Ladder && Word Ladder II
Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
思想：宽度优先搜索(BFS)即可。（可从头往尾部搜，也可从尾往头部搜，）。
我的方案中，使用两个 hash_set 分别存储当前层和下一层结点，另一个 hash_set存储之前遍历过的结点。
class Solution {public: int ladderLength(string start, string end, unordered_set<string> &dict) { int ans = 0; unordered_set<string> previousNodes; vector<unordered_set<string> > node_levels(2); int curLevel = 0; // which is index belong to vector node_levels. node_levels[curLevel].insert(end); ans++; unordered_set<string>::iterator it; while(!node_levels[curLevel].empty()) { for(it = node_levels[curLevel].begin(); it != node_levels[curLevel].end(); ++it) { for(size_t i = 0; i < it->size(); ++i) { string node(*it); for(node[i] = ‘a‘; node[i] <= ‘z‘; ++node[i]) { if(node == start) return (ans+1); // output 1 if(previousNodes.count(node) || node_levels[curLevel].count(node) || node[i] == (*it)[i] || !dict.count(node)) continue; node_levels[!curLevel].insert(node); } } previousNodes.insert(*it); } node_levels[curLevel].clear(); curLevel = !curLevel; ans++; } return 0; // output 2 }};
Word Ladder II
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
Return
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
思想： 在 I 的基础之上， 加入 hash_map 记下每条边， 从 end 开始搜索，建立以 start 为源点，end 为汇点的图，然后从 start 开始深搜即可。
typedef pair<string, string> PAIR;void getSolution(string &end, string& word, unordered_multimap<string, string> &map, vector<vector<string> > &vec, vector<string> &vec2) { if(word == end) { vec.push_back(vec2); vec.back().push_back(word); return; } pair<unordered_map<string, string>::iterator, unordered_map<string, string>::iterator> ret; ret = map.equal_range(word); while(ret.first != ret.second) { vec2.push_back(ret.first->first); getSolution(end, ret.first->second, map, vec, vec2); vec2.pop_back(); ret.first++; }}class Solution {public: vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) { vector<vector<string>> vec; unordered_multimap<string, string> edges; unordered_set<string> previousNodes; vector<unordered_set<string> > node_levels(2); int curLevel = 0; // an index belong to vector node_levels node_levels[curLevel].insert(end); unordered_set<string>::iterator it; while(!node_levels[curLevel].empty() && node_levels[curLevel].count(start) == 0) { for(it = node_levels[curLevel].begin(); it != node_levels[curLevel].end(); ++it) { for(size_t i = 0; i < it->size(); ++i) { string node(*it); for(node[i] = ‘a‘; node[i] <= ‘z‘; ++node[i]) { if(node == start) { node_levels[1-curLevel].insert(node); edges.insert(PAIR(start, *it)); break; } if(previousNodes.count(node) || node_levels[curLevel].count(node) || dict.count(node) == 0) continue; node_levels[1-curLevel].insert(node); edges.insert(PAIR(node, *it)); } } previousNodes.insert(*it); } node_levels[curLevel].clear(); curLevel = !curLevel; } previousNodes.clear(); if(node_levels[curLevel].empty()) return vec; vector<string> vec2; getSolution(end, start, edges, vec, vec2); return vec; }};
18. Word Ladder && Word Ladder II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。