LeetCode: Word Ladder II (Depth-search based)

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"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:

We are going to propose two different solutions: one based on the depth-search and one based on the A* algorithm (http://en.wikipedia.org/wiki/A*_search_algorithm).

Depth-search based

We use a first search based, as we need all the possible solution we stop the algorithm when we have finish processing the depth-level where we find the solution (we use an empty string to mark that we have finish processing a depth-level).  

We use a backtrack map to recover the possible paths, this recovered is done recursively.

To avoid visiting a node more than once we use two sets for the visited nodes, one for the nodes visited in previous levels and one for the ones in the same, the reason for having both instead of only one is that if it is in the same level the backtrack map has to include the possible path but in the case the node was visited in a previous level we do not have to include it.

Code:

public class Solution {
   public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict)    {      ArrayList<ArrayList<String>> solution = new ArrayList<ArrayList<String>>();      if(start.length()==0|| start == null || end == null)         return solution;

      LinkedList<String> queue = new LinkedList<String>();      
      HashSet<String> used = new HashSet<String>();      
      HashSet<String> levelUsed = new HashSet<String>();

      //backtrack map
      HashMap<String, ArrayList<String>> predecessors = new HashMap<String, ArrayList<String>>(); 

      queue.add(start);

      used.add(start);

      queue.add("");

      boolean finished = false;

      while(!queue.isEmpty())

      {

         String temp = queue.removeFirst();

         if (temp.equals(end))

            finished=true;

         if (temp.length()==0)

         {

            if (finished)

            {

               createSolution(end, start, predecessors, solution, new ArrayList<String>());

               return solution;

            }

            if(!queue.isEmpty())

            {

               queue.add("");

               used.addAll(levelUsed);

               levelUsed = new HashSet<String>();

            }

         }

         else

         {

            char[] chars = temp.toCharArray();

            for(int i=0; i<temp.length(); i++)

            {

               char original = chars[i];

               for(char c='a'; c<='z'; c++)

               {

                  if (original==c)

                     continue;

                  chars[i]=c;

                  String attempt = new String(chars);

                  if (dict.contains(attempt) && !(used.contains(attempt)) )

                  {

                     if(!levelUsed.contains(attempt))

                     {

                        queue.add(attempt);

                        levelUsed.add(attempt);

                     }

                     if(!predecessors.containsKey(attempt))

                     {

                        ArrayList<String> pred = new ArrayList<String>();

                        pred.add(temp);

                        predecessors.put(attempt, pred);

                     }

                     else

                        predecessors.get(attempt).add(temp);

                  }

               }

               chars[i]=original;

            }

         }

      }

      return solution;

   }   

   private void createSolution(String pointer, String start, HashMap<String, ArrayList<String>> predecesors, ArrayList<ArrayList<String>> solution, ArrayList<String> tempSolution)   {      tempSolution.add(0,pointer);

      if (pointer.equals(start))

      {

         solution.add(tempSolution);

         return;

      }

      for(String s: predecesors.get(pointer))

      {

         ArrayList<String> temp2 = (ArrayList<String>) tempSolution.clone();

         createSolution(s, start, predecesors, solution, temp2);

      }

   }
}