题目描述
Given two
words (start
and end),
and a dictionary, find
the length of shortest transformation sequence
from start
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 length5.
Note:
Return
0 if there
is no such transformation sequence.
All
words have
the same
length.
All
words contain only lowercase alphabetic
characters.
思路
思路是我们需要构造出一条路径，在这条路径上从start到end，每次只能变动当前节点的一个字母，构造出一个新单词，看这个单词是否在字典中，并且把这个新单词加入到当前的邻居中，也就是加一条边。利用BFS，由于BFS是一层一层的搜索。所以得出来的路径长度当然也是最短的。设单词长度为k，每个字母替换26次，BFS的复杂度为O(n)，则总的复杂度为（26*k*n）。
java代码
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class Solution2 {
public int ladderLength(String start, String end, HashSet<String> dict) {
Queue<String> q =
new LinkedList<String>();
Map<String, Boolean> visited =
new HashMap<String, Boolean>();
q.add(start);
int length =
1;
visited.put(start,
true);
int count1 =
1;
int count2 =
0;
while (!q.isEmpty()) {
length++;
for (
int i =
0; i < count1; i++) {
String current = q.poll();
for (
int j =
0; j < current.length(); j++) {
char[] strCharArr = current.toCharArray();
for (
char ch =
'a'; ch <=
'z'; ch++) {
if (strCharArr[j] == ch) {
continue;
}
strCharArr[j] = ch;
String newWord =
new String(strCharArr);
if (dict.contains(newWord) && newWord.equals(end) !=
true && !visited.containsKey(newWord)) {
visited.put(newWord,
true);
q.add(newWord);
count2++;
}
if (newWord.equals(end))
return length;
}
}
}
count1 = count2;
count2 =
0;
}
return 0;
}
public static void main(String[] args) {
String start =
"hit";
String end =
"cog";
HashSet<String> dict =
new HashSet<String>();
dict.add(
"hot");
dict.add(
"dot");
dict.add(
"dog");
dict.add(
"lot");
dict.add(
"log");
System.out.println(
new Solution2().ladderLength(start, end, dict));
}
}
