World Ladder II

This article is for self education:

 

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

 

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"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

The diagram below shows the graph that represents the connectivity among words. As shown in the diagram we want to go from red to tax. While backtracking on this graph, we will also cover the edges upwards that is from the tad to ted similarly from tex we will traverse to ted as well as rex. The key observation here is that going back in the upward direction will never lead us to the shortest path. We should always traverse the edges in the direction of beginWord to endWord.  To ensure that we never traverse up the ladder, let's use directed edges to connect the words. The edges in the graph below are all directed towards endWord. Also, notice that graphs produced by BFS do not contain cycles. Thus, the graph will be a Directed Acyclic Graph (DAG).  Now for the easy part, think of the previous graph as a bunch of layers and observe that once we reach a particular layer we don't want the future words to have the connection back to this layer. We will build our DAG using BFS. We will then add all the directed edges from the words present in the current layer and once all words in this layer have been traversed, we will remove them from the wordList. This way we will avoid adding any edges that point towards beginWord.

After constructing the graph, we can use our same backtracking approach to find the shortest paths between beginWord and endWord. Also, note that in the graph all paths between beginWord and endWord, obtained through BFS, will be the shortest possible. This is because all the edges in the graph will be directed in the direction of beginWord to endWord. Furthermore, there will not be any edge between the words that are on the same level. Therefore, iterating over any edge will bring us one step closer to the endWord, thus there is no need to compare the length of the path each time we reach the endWord.

Algorithm

1. Store the words present in wordList in an unordered set so that the words can be efficiently removed during the breadth-first search.

2. Perform the BFS, and add the edges to the adjacency list adjList. Also once a level is finished remove the visited words from the wordList.

3. Start from beginWord and while keep tracking of the current path as currPath traverse all the possible paths, whenever the path leads to the endWord store the path in shortestPaths.

Implementation

NOTE:

In the following implementation, for convineince, instead for go from beginWord to endWord, we go from endWord to beginWord.

After constructing the graph, we can use our same backtracking approach to find the shortest paths between beginWord and endWord. Also, note that in the graph all paths between beginWord and endWord, obtained through BFS, will be the shortest possible. This is because all the edges in the graph will be directed in the direction of beginWord to endWord. Each edge differing two word by one character. Furthermore, there will not be any edge between the words that are on the same level. Therefore, iterating over any edge will bring us one step closer to the endWord, thus there is no need to compare the length of the path each time we reach the endWord.

class Solution {

    

    List<List<String>> shortestPaths=new ArrayList<>();

    List<String> currPath=new ArrayList<String>();

    Map<String,List<String>> adjList=new HashMap<>();

    

     public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

         //1. Remove repeated word from the word list

         Set<String> wordSet=new HashSet<>(wordList);

         

         //2. Build adjacency list by BFS 

         bfs(beginWord, endWord, wordSet);

         

         //3. Init the path

         currPath.add(endWord);

         

         //4. backtracking from end word to find all possible paths. Note: all path leading to start word are shortest paths, because BFS ensures the paths are          //shortest to reach the destination. Each edge differs two nodes by one character         

         backtrack(endWord,beginWord);         

         return shortestPaths;         

     }

    

    private void bfs(String beginWord, String endWord, Set<String> wordSet){

        Queue<String> q=new LinkedList<>();

        q.add(beginWord);

        

           if (wordSet.contains(beginWord)) {  //correction3

                wordSet.remove(beginWord);

             }

        

         Map<String, Integer> isqueued=new HashMap<>();

        isqueued.put(beginWord,1);

        

        while(!q.isEmpty()){

            //to remove visited word from the set

            List<String> visited=new ArrayList<>();

           

            

            for(int i=q.size()-1; i>=0; i--){

                String currWord=q.peek();

                q.remove();

                

                List<String> neighbors=findNeighbors(currWord,wordSet);

                

                for(String word:neighbors){

                    visited.add(word);

                    

                    if(!isqueued.containsKey(word)){

                        isqueued.put(word,1);

                        q.add(word);  //correction4

                    }

                    

                    if(!adjList.containsKey(word)){

                        adjList.put(word, new ArrayList<String>());

                    }

                    

                    adjList.get(word).add(currWord);

                    

                }                

                                

            }    

            wordSet.remove(visited);

            

            for (int i = 0; i < visited.size(); i++) {

                if (wordSet.contains(visited.get(i))) {

                    wordSet.remove(visited.get(i));

                }

            }

        }

        }   

    }