例题分析 -- Word Latter

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.

*************************************************************************

分析：

        每一层查找一步可达的item，并保存；

        每一层访问完层数加1。

*************************************************************************

注意事项：

        何时停止，越早越好

        何时将访问过的点保存，越早越好

*************************************************************************

    public int ladderLength(String start, String end, Set<String> dict) {
        if (start.length() != end.length()) return 0;
        Queue<String> q = new LinkedList<String>();
        Queue<String> qNext = new LinkedList<String>();
        Queue<String> qTemp = null;
        Set<String> set = new HashSet<String>();
        int count = 1;
        q.add(start);
        while (!q.isEmpty()) {
            String item = q.poll();
            //set.add(item);
            char []cs = item.toCharArray();
            for (int i = 0; i < item.length(); i++) {

                // change one char
                for (char c = 'a'; c <= 'z'; c++) {
                    cs[i] = c;
                    String temp = new String(cs);
                    if (temp.equals(end)) return count + 1;
                    // not visit yet
                    if (dict.contains(temp) && !set.contains(temp)) {
                        qNext.add(temp);
                        set.add(temp);
                    }
                    cs[i] = item.charAt(i);
                }
            }
            if (q.isEmpty()) {
                qTemp = qNext;
                qNext = q;
                q = qTemp;
                count++;
            }
        }
        return 0;
    }