[Leetcode] Word Ladder II

Problem

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example, given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Algorithm

The shorted transformation sequences might be more than 1, but they all have the same length to start word.

Build a hash map <key, value> = <String, List<String>> , where List<String> is the transformation sequence from start to key. 

Put start and the path to start to the map. 

For each word in curLevel curStr

     For each transformed word nextStr

          if(nextStr in dict) 

               if(nextStr Not in map)

                       put<nextStr, path to nextStr> to map

               else

                       update nextStr' path

Above algorithm can pass small test case in OJ of Leetcode. However, it gets Time Exceed Limit for large test cases. 

         

Consider a path from start to end, for each intermediate word, we stored a sequence. Therefore, we used O(n^2) space to store the sequence in this path. There are many paths when we do BFS, so we waste a lot time to create and update the sequences. 

Previous Pointer

A path from start to end can be represented by previous pointers. Since there might be many path to end, we need an array of previous pointers for each word. Create a Node class, which has a label to store the word it represents, and an array of Nodes to store its previous pointers. The main structure of the code is the same as above, except for we update the previous pointers instead of the sequence of strings. 

Code

WordLadderII_Test cannot pass large dataset, resulting in TEL.