赞
踩
给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列,返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:
[
[“hit”,“hot”,“dot”,“dog”,“cog”],
[“hit”,“hot”,“lot”,“log”,“cog”]
]
本题和 Leetcode 127. 单词接龙 的区别是:需要打印单词转换过程。
为了能够打印,本题较 Leetcode 127
做出如下改变: 队列中的每个节点中保存的是从起点开始的所有路径。
对于每次取出的节点 now
,每个节点都是一个数组,数组中的最后一个元素为当前路径的最后节点 last
:
BFS
本来就是一步得到最短路径,而不像 DFS
那样迭代得到最短距离】to
)中满足 cost[to]>=cost[now]+1
的加入队列,并更新 cost[to]=cost[last]+1
。如果 cost[to]<cost[now]+1
,说明这个节点已经被访问过,不需要再考虑。const int INF = 1 << 20; class Solution { private: unordered_map<string, int> wordId; vector<string> idWord; vector<vector<int>> edges; public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { int id = 0; for (const string& word : wordList) { if (!wordId.count(word)) { wordId[word] = id++; idWord.push_back(word); } } if (!wordId.count(endWord)) { return {}; } if (!wordId.count(beginWord)) { wordId[beginWord] = id++; idWord.push_back(beginWord); } edges.resize(idWord.size()); for (int i = 0; i < idWord.size(); i++) { for (int j = i + 1; j < idWord.size(); j++) { if (transformCheck(idWord[i], idWord[j])) { edges[i].push_back(j); edges[j].push_back(i); } } } const int dest = wordId[endWord]; vector<vector<string>> res; queue<vector<int>> q; vector<int> cost(id, INF); q.push(vector<int>{wordId[beginWord]}); cost[wordId[beginWord]] = 0; while(!q.empty()){ vector<int> now = q.front(); q.pop(); int last = now.back(); if (last == dest) { vector<string> tmp; for (int index : now){ tmp.push_back(idWord[index]); } res.push_back(tmp); } else { for (int i = 0; i < edges[last].size(); i++) { int to = edges[last][i]; if (cost[last] + 1 < cost[to]) { cost[to] = cost[last] + 1; vector<int> tmp(now); tmp.push_back(to); q.push(tmp); } } } } return res; } bool transformCheck(const string& str1, const string& str2) { int differences = 0; for (int i = 0; i < str1.size() && differences < 2; i++) { if (str1[i] != str2[i]) { ++differences; } } return differences == 1; } };
[1] Leetcode 126. 单词接龙 II
[2] 官方题解
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。