从hit到cog之间有许多路径,我们可以将其想像成一个图:
两种方法:
- BFS记录每个单词所在层再DFS,
176ms, 2924KB
- 构建图再回溯,
156ms, 4580KB
方法一:BFS记录图中单词所在层再DFS
先通过BFS记录图里面单词所在的层,然后通过DFS找到所有的路径:
- BFS过程中需要记录历史节点及当前层次,最终获取每一个单词对应的层级
- DFS的终止条件是搜索到了结束单词
// // Created by jt on 2020/9/23. // #include <vector> #include <string> #include <queue> #include <map> #include <unordered_map> #include <unordered_set> using namespace std; class Solution { public: vector<vector<string>> findLadders(string start, string end, vector <string> &dict) { vector<vector<string>> res; // 建立单词与其相邻单词的map unordered_set<string> uset(dict.begin(), dict.end()); if (uset.count(end) == 0) return res; uset.insert(start); uset.insert(end); unordered_map<string, vector<string>> wordMap; for (auto it = uset.begin(); it != uset.end(); ++it) { for (int i = 0; i < it->size(); ++i) { for (int c = 'a'; c <= 'z'; ++c) { if (it->data()[i] == c) continue; string str = it->data(); str[i] = c; if (uset.count(str) != 0) { wordMap[it->data()].push_back(str); } } } } // 广度优先遍历记录每个单词所在层 unordered_map<string, int> visitedLevel; queue<string> qu; qu.push(start); int level = 1, quSize = 1; // level既是当前层级,也是[最短路径长度-1] visitedLevel[start] = 1; while (!qu.empty()) { if (visitedLevel.count(end) && visitedLevel[end] <= level) break; string str = qu.front(); qu.pop(); for (auto &a : wordMap[str]) { if (visitedLevel.count(a) == 0) { visitedLevel[a] = level + 1; qu.push(a); } } if (--quSize == 0) { level++; quSize = qu.size(); } } // 深度优先遍历查找所有最短路径 vector<string> vec = {start}; dfs(res, visitedLevel, wordMap, vec, end); return res; } void dfs(vector<vector<string>> &res, unordered_map<string, int> &visitedLevel, unordered_map<string, vector<string>> &wordMap, vector<string> &vec, string target) { if (vec[vec.size()-1] == target) { res.push_back(vec); return; } string word = vec[vec.size()-1]; for (auto &str : wordMap[word]) { if (visitedLevel.count(str) && visitedLevel[str] == vec.size()+1) { vec.push_back(str); dfs(res, visitedLevel, wordMap, vec, target); vec.pop_back(); } } } };
方法二:构建图再回溯
整体方案:
- 从hit开始构造这个图
- 然后从cog出发,反向查找出所有的最短路径
构造图的思路:
- 首先,可以获取每个单词变更一个字母后在输入字典中的所有对应单词,如
dot
对应lot/hot/dog
- 利用BFS从起始节点开始填充它的下一层节点,如果某个单词已经在本层或者上面的层出现过,那么忽略之
- 如果出现了终止单词,记录终止节点的位置
注:举例说明第2点,如果当前节点的单词为
dot
,对应的下一层节点的单词为lot/hot/dog
,但是其中lot
与dot
在同一层,甚至更高层,则可以忽略lot
反向回溯的思路:
- 从终止节点出发进行回溯(DFS),如果找到了起始单词,将当前路径加入结果
- 输出最短路径对应的结果
代码如下:
// // Created by jt on 2020/9/23. // #include <vector> #include <string> #include <queue> #include <unordered_map> #include <unordered_set> #include <algorithm> using namespace std; // 存储图的节点 struct GraphNode{ string word; vector<GraphNode*> parents; vector<GraphNode*> sons; GraphNode(string w): word(w) {} }; class Solution { public: vector<vector<string>> findLadders(string start, string end, vector <string> &dict) { vector<vector<string>> res; // 构建每个单词与其他单词的转换关系 if (dict.empty() || start.size() < 1 || end.size() < 1) return res; unordered_set<string> unorderedSet(dict.begin(), dict.end()); unorderedSet.insert(start); unorderedSet.insert(end); unordered_map<string, vector<string>> wordMap; for (auto it = unorderedSet.begin(); it != unorderedSet.end(); ++it) { for (int i = 0; i < it->size(); ++i) { for (char a = 'a'; a <= 'z'; ++a) { if (a == it->data()[i]) continue; string str = it->data(); str[i] = a; if (unorderedSet.count(str) != 0) { if (wordMap.count(it->data())) wordMap[it->data()].push_back(str); else wordMap[it->data()] = {str}; } } } } // 构建图 unordered_map<string, GraphNode*> visitedPointer; // 记录已经出现过的单词,以及对应的指针 unordered_map<string, int> visitedLevel; // 记录已经出现过的单词,以及对应的层级 queue<GraphNode*> qu; GraphNode *head = new GraphNode(start), *tail = nullptr; visitedPointer[start] = head; visitedLevel[start] = 0; qu.push(head); int level = 0, cnt = 1; // 记录当前层的ID以及节点个数 while (!qu.empty()) { GraphNode *p = qu.front(); qu.pop(); for (auto str : wordMap[p->word]) { GraphNode *node; if (visitedPointer.count(str) != 0) { // 如果单词出现在本层甚至更高层级,略过 if (visitedLevel[str] <= level) continue; else node = visitedPointer[str]; } else { node = new GraphNode(str); if (str == end) tail = node; // 如果是终止单词,记录尾部节点 visitedPointer[str] = node; visitedLevel[str] = level + 1; qu.push(node); } node->parents.push_back(p); p->sons.push_back(node); } // 更新层ID if (--cnt == 0) { level++; cnt = qu.size(); } } // 反向回溯图 vector<string> vec = {end}; // 存储路径 dfs(tail, vec, res); return res; } void dfs(GraphNode *node, vector<string> &vec, vector<vector<string>> &res) { if (!node) return; if (node->parents.empty()) { reverse(vec.begin(), vec.end()); res.push_back(vec); reverse(vec.begin(), vec.end()); return; } for (auto p : node->parents) { vec.push_back(p->word); dfs(p, vec, res); vec.pop_back(); } } };