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

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 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.

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(start == null || end == null || start.equals(end)) return 0;

        

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

        HashSet<String> record = new HashSet<String>();

        from.offer(start);

        record.add(start);

        int count = 1;

        while(!from.isEmpty()){

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

            while(!from.isEmpty()){

                String word = from.poll();

                if(word.equals(end)) return count;

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

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

                        char[] arr = word.toCharArray();

                        if(arr[i] != c){

                            arr[i] = c;

                            String newWord = new String(arr);

                            if(end.equals(newWord)) return count+1;

                            if(!record.contains(newWord) && dict.contains(newWord)){

                                record.add(newWord);

                                to.add(newWord);

                            }

                        }

                    }

                }

            }

            count++;

            from = to;

        }

        return count;

    }

}