Given two words (startandend), and a dictionary, find the length of shortest transformation sequence fromstarttoend, such that:

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

Notice

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

Have you met this question in a real interview?

Yes

Example

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

As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length5.

1. it is a hidden graph as we can map it out as a graph

hit -> hot -> lot

 -> dot -> lot

            -> dog -> cog

the trick is we can form the next word based on the alpabetical order for each char of the word as the length of the dict could get really long. and we only need to gather the next word list along the path. so a standard simple graph shortest distance problem

public class Solution {
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    public int ladderLength(String start, String end, Set<String> dict) {
        // write your code here
        if (dict == null || dict.size() == 0) {
            return 0;
        }

        if (start.equals(end)) {
            return 1;
        }

        dict.add(start);
        dict.add(end);

        HashSet<String> isVisited = new HashSet<String>();
        Queue<String> queue = new LinkedList<>();

        int count = 1;
        queue.offer(start);
        isVisited.add(start);

        //start bfs
        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;
            //need to do this in level
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();

                //now get the next stringlist
                for (String next : getNextStringList(cur, dict, isVisited)) {
                    if (next.equals(end)) {
                        return count;
                    }

                    if (isVisited.contains(next)) {
                        continue;
                    }

                    queue.offer(next);
                    isVisited.add(next);
                }
            }
        }
        return 0;
    }

    public ArrayList<String> getNextStringList(String word, 
                                               Set<String> dict,
                                               HashSet<String> isVisited) {
        ArrayList<String> ans = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            for (char j = 'a'; j < 'z'; j++) {
                if (j == word.charAt(i)) {
                    continue;
                }

                String newWord = replace(word, i, j);

                if (!isVisited.contains(newWord) && dict.contains(newWord)) {
                    ans.add(newWord);
                }
            }
        }

        return ans;
    }

    public String replace(String word, int index, char x) {
        char[] chars = word.toCharArray();
        chars[index] = x;

        return new String(chars);
    }
}