• 博客访问： 106476
• 博文数量： 41
• 博客积分： 0
• 博客等级： 民兵
• 技术积分： 407
• 用 户 组： 普通用户
• 注册时间： 2013-06-27 13:42

2016年（1）

2015年（18）

2014年（22）

2014-12-01 11:10:24

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。

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

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

1.     public int ladderLength(String start, String end, Set<String> dict) {
2.         if (start.length() != end.length()) return 0;
3.         Queue<String> q = new LinkedList<String>();
4.         Queue<String> qNext = new LinkedList<String>();
5.         Queue<String> qTemp = null;
6.         Set<String> set = new HashSet<String>();
7.         int count = 1;
9.         while (!q.isEmpty()) {
10.             String item = q.poll();
12.             char []cs = item.toCharArray();
13.             for (int i = 0; i < item.length(); i++) {
14.
15.                 // change one char
16.                 for (char c = 'a'; c <= 'z'; c++) {
17.                     cs[i] = c;
18.                     String temp = new String(cs);
19.                     if (temp.equals(end)) return count + 1;
20.                     // not visit yet
21.                     if (dict.contains(temp) && !set.contains(temp)) {
24.                     }
25.                     cs[i] = item.charAt(i);
26.                 }
27.             }
28.             if (q.isEmpty()) {
29.                 qTemp = qNext;
30.                 qNext = q;
31.                 q = qTemp;
32.                 count++;
33.             }
34.         }
35.         return 0;
36.     }