Word Ladder
Feb 11
10499 / 37276
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence fromstart to
end, such that:
- Only one letter can be changed at a time
- 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
public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
HashSet<String> used = new HashSet<String>();
int step = 1;
int l1 = 1,l2 = 0; //很重要！ 用来记录当前的层数。。
while (queue.size() != 0) {
String s = queue.poll(); //
// System.out.println("now=" + s);
used.add(s); // 忘记放到used里面了...
// System.out.println(used.size());
HashSet<String> strs = getNext(s,end, dict, used);
l2+=strs.size();
l1--;
for (String ss : strs) {
if (ss.equals(end)) {
return step + 1;
} else {
queue.offer(ss); //写错了》。。。
}
}
if(l1==0){
step++;
l1 = l2;
l2 = 0;
}
}
return 0;
}
public HashSet<String> getNext(String s, String end,HashSet<String> dict,
HashSet<String> used) {
if (s == null)
return null;
HashSet<String> set = new HashSet<String>();
for (int i = 0; i < s.length(); i++) {
StringBuilder now = new StringBuilder(s); //
for (char c = 'a'; c <= 'z'; c++) {
now.setCharAt(i, c); //
// System.out.println("@@"+now.toString());
if (end.equals(now.toString())||dict.contains(now.toString())
&& !used.contains(now.toString())) { // toString!!!!!!!!!
set.add(now.toString()); //
//System.out.println("next" + now.toString());
}
}
}
return set;
}
}