Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
找最短距离用BFS，找具体路径用DFS。先用BFS生成地图childrens，指明从start到end每层的每个点下一步可以遍历哪些点。为了进一步刨除不能遍历的点，交替进行两头的BFS: 每次选择空间少的那个继续遍历下一层，当俩交汇时说明已经遍历到最后一层。再根据地图从start做DFS。或者用map记录节点到终点的距离，DFS时跳过不符合最短距离的点。
Copy /*
* @lc app=leetcode id=126 lang=cpp
*
* [126] Word Ladder II
*/
class Solution {
public:
unordered_map<string, unordered_set<string>> bfs(unordered_set<string> &words, const string start, const string end) {
unordered_set<string> q1({start});
unordered_set<string> q2({end});
unordered_map<string, unordered_set<string>> childrens;
bool found = false, backward = false;
while (!q1.empty() && !q2.empty() && !found) {
for (const auto &w : q1) words.erase(w);
for (const auto &w : q2) words.erase(w);
unordered_set<string> nq;
if (q1.size() > q2.size()) {
swap(q1, q2);
backward = !backward;
}
for (const auto &t : q1) {
auto w = t;
for (int i = 0; i < t.size(); ++i) {
const char ch = w[i];
for (char c = 'a'; c <= 'z'; ++c) {
w[i] = c;
const auto *parent = &t;
const auto *child = &w;
if (backward) swap(parent, child);
if (q2.count(w)) {
found = true;
childrens[*parent].insert(*child);
} else if (words.count(w)) {
childrens[*parent].insert(*child);
nq.insert(w);
}
}
w[i] = ch;
}
}
swap(q1, nq);
}
return childrens;
}
void dfs(unordered_map<string, unordered_set<string>> &childrens, const string end, const string cur, vector<string> &path, vector<vector<string>> &res) {
if (cur == end) {
res.push_back(path);
return;
}
for (const auto &c : childrens[cur]) {
path.push_back(c);
dfs(childrens, end, c, path, res);
path.pop_back();
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return {};
auto childrens = bfs(words, beginWord, endWord);
vector<string> path({beginWord});
vector<vector<string>> res;
dfs(childrens, endWord, beginWord, path, res);
return res;
}
};
Errors:
1. 每次动态计算neighbors很花时间, TLE
时间复杂度O(N), N为dict长度. 因为所生成的递归树每个节点是一个word, 最多有O(N)个节点.
还可以只用BFS. 这时 BFS存的就不再是单个的node, 而是一条path.
注意题意要求返回最短的路径, 也就是说所有在当前层和之前层出现过的节点都无需在未来层出现, 否则相当于在访问过某点后又重新引入该点(无论是否在同一条path), 无谓的增加了长度. 比如当前访问了 [a, c] a的下一个点是c, 那[a, c]和c之后将访问一样的点, 只是前者无意义的引入了a.
Copy class Solution {
// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch ='a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch) continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
Set<String> dict = new HashSet<String>(wordList);
if (!dict.contains(endWord)) {
return res;
}
dict.add(beginWord);
Queue<List<String>> queue = new LinkedList<>();
Map<String, List<String>> nodeNeighbors = new HashMap<>();
List<String> spath = new ArrayList<>();
spath.add(beginWord);
queue.add(spath);
boolean found = false;
Set<String> wordsPerLevel = new HashSet<String>();
while (!queue.isEmpty()) {
if (found) {
break;
}
int size = queue.size();
wordsPerLevel.clear();
List<List<String>> list = (List)queue;
for (int i = 0; i < size; i++) {
List<String> path = list.get(i);
wordsPerLevel.add(path.get(path.size() - 1));
}
dict.removeAll(wordsPerLevel);
for (int i = 0; i < size; i++) {
List<String> path = queue.poll();
String str = path.get(path.size() - 1);
if (str.equals(endWord)) {
res.add(path);
found = true;
continue;
}
for (String neighbor : getNeighbors(str, dict)) {
List<String> newPath = new ArrayList<>(path);
newPath.add(neighbor);
queue.add(newPath);
}
}
}
return res;
}
}