126. Word Ladder II - cocoder39/coco39_LC GitHub Wiki
tips:
-
- BFS: Instead of tracking the each node at last layer, tracking the paths to each of those node. At each new layer, updating the paths to each node at current layer using the paths from last layer
-
- Once a node is visited in current layer, it should be removed from wordSet to avoiding re-visiting it
Time complexity: suppose there are N words, each word has length of K, the length of the shortest ladder is L, there are M paths that can reach each word
T = O(N * K * 26 * (K + M * L * K)) = O(N * M * L * K^2)
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
LETTERS = "abcdefghijklmnopqrstuvwxyz"
k = len(beginWord)
wordSet = set(wordList)
layer = collections.defaultdict(list)
layer[beginWord].append([beginWord])
while layer:
if endWord in layer:
return layer[endWord]
newLayer = collections.defaultdict(list)
for lastWord in layer: # at most N words at current layer
for i in range(k): # K
for ch in LETTERS: # 26
newWord = lastWord[:i] + ch + lastWord[i+1:] # K
if newWord in wordSet:
for ladders in layer[lastWord]: # M
newLayer[newWord].append(ladders + [newWord]) # L*K
wordSet -= newLayer.keys()
layer = newLayer
======================================================================================================
find one shortest path 127. Word Ladder
- shortest path => bfs => queue
- once found a next-level node, erase it from wordList since we have got its shortest distance from source. It may be next-level node of another node at current level, but it doesn't matter because we only care about the distance.
find all the shortest paths
- shortest path => bfs => unordered_set. if more than one node share the same next-level node, we would push duplicates into queue
- erase next-level nodes from wordList after finding out all nodes in next level, cannot erase a next-level node immediately after finding it because a next-level node can be the next-level node of more than one node. we need build the relationship between current-level nodes and next-level nodes rather than just get the distance of next-level nodes
it takes O(V * len) to build the graph using BFS. if dfs from endWord, then searching branch is useful in the final result, thus the search space is no more than O(V * len). Then total time is O(V * LEN)
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
if (beginWord == endWord) {
return {{beginWord}};
}
unordered_map<string, vector<string>> map; //map[cur] => next
unordered_set<string> curLevel, nextLevel;
curLevel.insert(beginWord);
bool found = false;
int dist = 1;
while (! found && ! curLevel.empty()) {
for (auto &cur : curLevel) {
wordList.erase(cur);
}
for (auto &cur : curLevel) {
for (int i = 0; i < cur.length(); i++) {
string next = cur;
for (char j = 'a'; j <= 'z'; j++) {
next[i] = j;
if (next == endWord) {
found = true;
map[cur].push_back(next);
} else if (wordList.find(next) != wordList.end()) {
nextLevel.insert(next);
map[cur].push_back(next);
}
}
}
}
curLevel = nextLevel;
nextLevel.clear();
dist++;
}
if (! found) {
return {};
}
vector<vector<string>> res;
vector<string> path;
path.push_back(beginWord);
dfs(res, path, map, dist, endWord);
return res;
}
private:
void dfs(vector<vector<string>>& res, vector<string>& path, unordered_map<string, vector<string>>& map, int dist, string& endWord) {
if (path.size() == dist && path.back() == endWord) {
res.push_back(path);
return;
} else if (path.size() >= dist) {
return;
}
string& cur = path.back();
for (auto &next : map[cur]) {
path.push_back(next);
dfs(res, path, map, dist, endWord);
path.pop_back();
}
}
};
optimization 1: when backtracking the path, we can start from endWord and move towards beginWord since endWord has fewer indegrees while beginWord has lots of outdegrees. One thing to mention is that once get a path, we need reverse the path then append to res. After that, reverse the path again to restore it, thus it would not impact previous searching level.
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
if (beginWord == endWord) {
return {{beginWord}};
}
unordered_map<string, vector<string>> map; //map[cur] => pre
unordered_set<string> curLevel, nextLevel;
curLevel.insert(beginWord);
bool found = false;
int dist = 1;
while (! found && ! curLevel.empty()) {
for (auto &cur : curLevel) {
wordList.erase(cur);
}
for (auto &cur : curLevel) {
for (int i = 0; i < cur.length(); i++) {
string next = cur;
for (char j = 'a'; j <= 'z'; j++) {
next[i] = j;
if (next == endWord) {
found = true;
map[next].push_back(cur);
} else if (wordList.find(next) != wordList.end()) {
nextLevel.insert(next);
map[next].push_back(cur);
}
}
}
}
curLevel = nextLevel;
nextLevel.clear();
dist++;
}
if (! found) {
return {};
}
vector<vector<string>> res;
vector<string> path;
path.push_back(endWord);
dfs(res, path, map, dist, beginWord);
return res;
}
private:
void dfs(vector<vector<string>>& res, vector<string>& path, unordered_map<string, vector<string>>& map, int dist, string& endWord) {
if (path.size() == dist && path.back() == endWord) {
reverse(path.begin(), path.end());
res.push_back(path);
reverse(path.begin(), path.end()); //a bug if ignore this
return;
} else if (path.size() >= dist) {
return;
}
string& cur = path.back();
for (auto &next : map[cur]) {
path.push_back(next);
dfs(res, path, map, dist, endWord);
path.pop_back();
}
}
};
optimization 2: bfs from both ends
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
vector<vector<string>> ladders;
vector<string> ladder;
unordered_map<string, vector<string>> children;//children[father_word] = child_word
unordered_set<string> beg_end; //bfs from beginWord
unordered_set<string> end_beg; //bfs from endWord
bool beg2end = true; //beg2end == true iff search direction is from startWord to endWord
beg_end.insert(beginWord);
end_beg.insert(endWord);
if (! two_end_bfs(beg_end, end_beg, beg2end, children, wordList))
return ladders;
ladder.push_back(beginWord);
genLadder(beginWord, endWord, children, ladder, ladders);
return ladders;
}
private:
bool two_end_bfs(unordered_set<string>& beg_end,
unordered_set<string>& end_beg,
bool beg2end,
unordered_map<string, vector<string>>& children,
unordered_set<string>& wordList) {
if (beg_end.empty()) return false; //no word for further bfs
if (beg_end.size() > end_beg.size()) //balance both ends
return two_end_bfs(end_beg, beg_end, ! beg2end, children, wordList); //reverse search direction
for (auto word : beg_end) wordList.erase(word); //get rid of words have been found
for (auto word : end_beg) wordList.erase(word);
unordered_set<string> nextLevel;
bool found = false;
for (auto word : beg_end) {
int len = word.length();
string next = word;
for (int i = 0; i < len; i++) {
char tmp = next[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == tmp) continue;
next[i] = c;
if (end_beg.find(next) != end_beg.end()) {//found the bridges of two ends
found = true;
beg2end ? children[word].push_back(next) : children[next].push_back(word);
}
else if (! found && wordList.find(next) != wordList.end()) {//spend time processing word on a longer path if without !found,
beg2end ? children[word].push_back(next) : children[next].push_back(word);
nextLevel.insert(next);
}
}
next[i] = tmp;
}
}
return found || two_end_bfs(end_beg, nextLevel, ! beg2end, children, wordList);
}
void genLadder(string begin, string end, unordered_map<string, vector<string>>& children, vector<string>& ladder, vector<vector<string>>& ladders) {
if (begin == end) {
ladders.push_back(ladder);
return;
}
for (auto child : children[begin]) {
ladder.push_back(child);
genLadder(child, end, children, ladder, ladders);
ladder.pop_back();
}
}
};