题目描述
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.
思路:
单词的转换是一个图,求边权值相同的最短路径可以使用广度优先搜索,最短路径长度就是层数。用队列保存搜索到的路径,每次拿到队头的节点,查找可达的下一个节点,并把节点从dict中取出,表示已经访问过了,将这些节点再入队。两个变量last和curLast分别表示上一次层的最后一个节点和当前层的最后一个节点。当发现从队列中出来的节点是上一层的最后一个节点时就把当前最后一个节点赋值给上一层最后节点,同时层数自增。当找到end节点时直接返回层数,当队列空了还没找到就返回0。
代码:
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
Queue<String> paths = new LinkedList<>();
paths.offer(start);
dict.remove(start);
// 初始层数为1
int level = 1;
String last = start;
String curLast = last;
while (!paths.isEmpty()){
String cur = paths.poll();
// 如果找到end节点,直接返回层数
if (cur.equals(end)) return level;
char[] str = cur.toCharArray();
// 把当前字符串的每一位都进行替换,看替换后的字符串是否在字典中
for (int i=0; i<str.length; i++){
char original = str[i];
for (char c='a'; c<='z'; c++){
str[i] = c;
String next = new String(str);
// 如果在就从字典中拿走,放入队列,同时当前层的最后节点需要更新
if (dict.contains(next)){
dict.remove(next);
paths.offer(next);
curLast = next;
}
}
str[i] = original;
}
// 如果当前队列中拿出的节点是上一层最后的节点,说明curLast已经是当前层真正的最后节点了
if (last.equals(cur)){
last = curLast;
level++;
}
}
return 0;
}
}
网友评论