Leetcode: Word Ladder

 Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:

We first preprocess the dictionary creating a hashmap that contains the list of neighbor words for each one.
Then we apply BFS keeping a set of the nodes already visited.

public class Solution {
    public int ladderLength(String start, String end, 
        HashSet<String> dict) 
    {
        HashMap<String, ArrayList<String>> neighbors = 
            new HashMap<String, ArrayList<String>>();
        for(String word: dict)
        {
            ArrayList<String> listNeighbors = new ArrayList<String>();
            StringBuilder attempt = new StringBuilder(word);
            for(int i=0; i<word.length(); i++)
            {
                for(char letter='a'; letter<='z'; letter++)
                {
                    if(word.charAt(i)==letter)
                        continue;
                    attempt.setCharAt(i,letter);
                    if(dict.contains(attempt.toString()))
                        listNeighbors.add(attempt.toString());
                }
                attempt.setCharAt(i,word.charAt(i));
            }
            neighbors.put(word,listNeighbors);
        }
        
        final String newLevel = "#";
        ArrayDeque<String> queue = new ArrayDeque<String>();
        HashSet<String> usedWords = new HashSet<String>();
        queue.add(start);
        queue.add(newLevel);
        usedWords.add(start);
        int levels = 1;
        while(!queue.isEmpty())
        {
            String actual = queue.remove();
            if(actual.equals(end))
                return levels;
            if(actual.equals(newLevel))
            {
                if(queue.isEmpty() || queue.peek().equals(newLevel))
                    return 0;
                queue.add(newLevel);
                levels++;
            }
            else
            {
                for(String neighbor: neighbors.get(actual))
                {
                    if(!usedWords.contains(neighbor))
                    {
                        queue.add(neighbor);
                        usedWords.add(neighbor);
                    }
                }
            }
        }
        return 0;
    }
}