Description

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.

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.

Solution

按层遍历queue— 先把当前的size记下来，然后poll size多次

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.equals(end)) {
            return 1;
        }
        int distance = 1;
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int size =  queue.size();
            for (int i = 0; i < size; i++) {
                String curStr = queue.poll();
                for (char c = 'a'; c <= 'z'; c++) {
                    for (int j = 0; j < curStr.length(); j++) {
                        if (curStr.charAt(j) != c)  {
                            String newStr = replace(curStr, j, c);
                            if (newStr.equals(end)) {
                                return distance + 1;
                            }

                            if (dict.contains(newStr)) {
                                queue.offer(newStr);
                                dict.remove(newStr);
                            }
                        }
                    }
                }
            }

            distance++;
        }

        return 0;
    }

    private String replace(String s, int index, char c) {
        return s.substring(0, index) + c + s.substring(index + 1);
    }
}