描述
给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列
比如：
1.每次只能改变一个字母。
2.变换过程中的中间单词必须在字典中出现。
注意事项
1.所有单词具有相同的长度。
2.所有单词都只包含小写字母。
样例
给出数据如下：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
返回
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
思路
先从end出发做start的BFS，再从start出发做end的DFS，一边走一边保证距离越来越近，也可以倒过来做因为是无向图，所以只需要保证路径顺序就可以了，一个方向BFS另一个方向DFS
代码
public class Solution {
public List<List<String>> findLadders(String start,
String end,
Set<String> dict) {
List<List<String>> ladders = new ArrayList<List<String>>();
Map<String, List<String>> map = new HashMap<String, List<String>>();
Map<String, Integer> distance = new HashMap<String, Integer>();
dict.add(start);
dict.add(end);
bfs(map, distance, start, end, dict);
List<String> path = new ArrayList<String>();
dfs(path, map, distance, end, start, ladders);
return ladders;
}
// 从起点开始进行bfs，bfs对map和distance都进行了初始化
private void bfs(Map<String, List<String>> map,
Map<String, Integer> distance,
String start,
String end,
Set <String> dict) {
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
distance.put(start, 0);
// 给dict中每一个单词映射一个新的hash数组
for (String s : dict) {
map.put(s, new ArrayList<String>());
}
while(!queue.isEmpty()) {
String crt = queue.poll();
List<String> nextList = getNextList(crt, dict);
for (String next : nextList) {
// 将当前单词加入到下一个单词的地图中
map.get(next).add(crt);
// distance中未标记的结点，在distance中标好距离，加入队列
if (!distance.containsKey(next)) {
distance.put(next, distance.get(crt) + 1);
queue.offer(next);
}
}
}
}
// 将当前单词变为字典中存在的下一个单词(两个单词差一个字母)，将从起点到终点一条路线上的所有单词全部加入到list
private List<String> getNextList(String crt, Set<String> dict) {
List<String> list = new ArrayList<String>();
for (char c = 'a'; c <= 'z'; c++) {
for (int i = 0; i < crt.length(); i++) {
if (c != crt.charAt(i)) {
String nextWord = crt.substring(0, i) + c
+ crt.substring(i + 1);
if (dict.contains(nextWord)) {
list.add(nextWord);
}
}
}
}
return list;
}
// 注意起始位置的变换要体现在接口参数中,从终点开始进行dfs，crt代表的是队列中抛出的点，bfs运行到最后crt代表的是终点
private void dfs(List<String> path,
Map<String, List<String>> map,
Map<String, Integer> distance,
String crt,
String start,
List<List<String>> ladders) {
// crt是从end开始搜索的，所以当crt为start的时候，一条逆序的有效的路径已经出来了，那么这里把这条路径翻转一下，放到结果中，之后再翻转一下以便之后其他路径的搜索
// 不可以把path.add(crt)加入到else里，因为每次递归都要remove，若写进else里并不会每次都把crt加入path，会造成动态数组下标越界
path.add(crt);
if (crt.equals(start)) {
Collections.reverse(path);
ladders.add(new ArrayList(path));
// 若不翻转回来的话，当退出一层dfs，执行完path.remove(path.size() - 1);会移除错误的单词
Collections.reverse(path);
} else {
for (String next : map.get(crt)) {
// 注意此处不是distance.get(next) == distance.get(crt) + 1，对下一个计算的单词要求是要distance里(并不是每个单词都在distance里)然后距离只有+1的差距
if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) {
dfs(path, map, distance, next, start, ladders);
}
}
}
path.remove(path.size() - 1);
}
}
