/**
*
* 126. Word Ladder II
* 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.
* Note:
*
* Return an empty list if there is no such transformation sequence.
* All words have the same length.
* All words contain only lowercase alphabetic characters.
* You may assume no duplicates in the word list.
* You may assume beginWord and endWord are non-empty and are not the same.
* Example 1:
*
* Input:
* beginWord = “hit”,
* endWord = “cog”,
* wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
*
* Output:
* [
* [“hit”,”hot”,”dot”,”dog”,”cog”],
* [“hit”,”hot”,”lot”,”log”,”cog”]
* ]
*/
See the solution on github here:
Before you start this question, please have a look at the question Word Ladder. This question builds on that. While the question “Word Ladder” was asking about the shortest sequence of words to get from start to end word, this question is asking for all shortest combination of words that get you from start to end.
The solution is not trivial but the approach used here is very elegant and thus needs to be understood and practiced.
Observation:
- Just as we did in WordLadder, we find mappings between a word and its possible combinations using “*” and traverse the combinations.
- We need to stop traversing levels when a combination is found
- We need to identify mappings between words which we can traverse to find the combination of words that get us to the end word once we start from the first word.
Algorithm:
- Run a two directional BFS from start to end
- Instead of a queue work with sets as you can do a search whether the desired word is found in the set
- Avoid cycles by trimming the words from possible words as you traverse them
- Add the mapping from source to target words
- During the two directional BFS choose to work on smaller of the two queues as it will help focus the search
- Stop when word found in the other queue. And determine the traversal level.
- Backtrack the mapping to determine the possible set of words
- During backtrack stop traversal when depth increases beyond the max level as determined above in step 6 above
Here is the code to run two directional BFS:
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
//build the possible mappings.
Map<String, List<String>> wordMappings = new HashMap<>();
for (String word : wordList) {
if (word.equals(beginWord)) continue;
for (int i = 0; i < word.length(); i++) {
String modWord = word.substring(0, i) + "*" + word.substring(i + 1);
List<String> words = wordMappings.computeIfAbsent(modWord, (l) -> new ArrayList<>());
words.add(word);
}
}
Set<String> vocabulary = new HashSet<>(wordList);
if (!vocabulary.contains(endWord)) {
return new ArrayList<>();
}
//a word may have more than one way to map to the next word, keeping these mappings in a set
//ensures we process each mapping from source to target word only once
Set<String> queue1 = new HashSet<>();
Set<String> queue2 = new HashSet<>();
queue1.add(beginWord);
queue2.add(endWord);
//the value in the map is a set instead of a list to ensure that we dont reprocess
//a mapping from source to target word more than once
Map<String, Set<String>> outMappings = new HashMap<>();
boolean isForward = true;
boolean found = false;
int pathLength = 1;
while (!queue1.isEmpty() && !found) {
pathLength++; //increase length of path forward
//remove words to be processed next and in the queue from vocab of words
//this is so that cycles are avoided
vocabulary.removeAll(queue1);
Set<String> newQueue = new HashSet<>();
for (String word : queue1) {
//find possible mappings for the given word
for (int i = 0; i < word.length(); i++) {
String modWord = word.substring(0, i) + "*" + word.substring(i + 1);
List<String> mappings = wordMappings.get(modWord);
if (mappings == null) continue;
for (String mapWord : mappings) {
//only process if the given word is included in our list of words to process
if (vocabulary.contains(mapWord)) {
if (queue2.contains(mapWord)) {
found = true; //if other queue has the mapped word than target has been found
}
newQueue.add(mapWord); //add the mapping
if (isForward) { //update mapping from source to destination word
Set<String> list = outMappings.computeIfAbsent(word, (l) -> new HashSet<>());
list.add(mapWord);
} else { //reverse for the end to forward BFS so mappings are in correct order
Set<String> list = outMappings.computeIfAbsent(mapWord, (l) -> new HashSet<>());
list.add(word);
}
}
}
}
}
queue1 = newQueue;
if (queue1.size() > queue2.size()) {
//swap the queues to use the queue with the smaller size. this ensures we converge towards the
//solution faster
isForward = !isForward; //update forward direction every time we swap queues
Set<String> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
}
if (!found) {
return new ArrayList<>();
}
List<List<String>> ans = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
path.add(beginWord);
//back track to find the possible paths.
backtrack(ans, path, beginWord, outMappings, endWord, pathLength);
return ans;
}
Here is code for backtracking:
void backtrack(List<List<String>> ans, LinkedList<String> path, String currWord, Map<String, Set<String>> mappings,
String endWord, int maxLength) {
if (path.size() > maxLength) {
return;
}
if (currWord.equals(endWord)) {
ans.add(new ArrayList<>(path));
return;
}
if (mappings.containsKey(currWord)) {
for (String word : mappings.get(currWord)) {
path.add(word);
backtrack(ans, path, word, mappings, endWord, maxLength);
path.removeLast();
}
}
}