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

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

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

这一题可以用用队列来解决,将下一次接龙的所有可能放进队列中,然后更新队列,继续看当前队列可以接到什么单词再放入队列中。已经进入过队列的单词不会再被接龙,循环往复直到队列中有end。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
int count = 0;
ArrayList<String> queue = new ArrayList<String>();

HashSet<String> d = new HashSet<String>(dict);
d.add(end);

queue.add(start);

Iterator iterator;

boolean changeable = true;

while (changeable) {

changeable = false;
ArrayList<String> newQueue = new ArrayList<String>();
for (String word:queue){
if(word.equals(end)){
return count + 1;
}

iterator = d.iterator();

while (iterator.hasNext()) {
String s = iterator.next().toString();
if (diff(word, s) == 1) {
changeable = true;
newQueue.add(s);
}
}

for (String s : newQueue){
d.remove(s);
}

}
queue = newQueue;
count++;

}

return 0;
}

public int diff(String s1, String s2) {

int res = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
res++;
}
}
return res;
}