题意
给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列
比如：
1、每次只能改变一个字母。
2、变换过程中的中间单词必须在字典中出现。
注意事项
所有单词具有相同的长度。
所有单词都只包含小写字母。
样例
给出数据如下：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
返回
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
解题思路
根据每两个单词是否只差一个字母，进行建图，然后如下。
1.深搜 + 回溯 + 记忆化（记录每个节点到 终结点 的最短转换序列），超时啦。。。
2.通过广搜 计算出终结点到各个节点的最短距离（包括源节点到终结点的最短距离，也就是和 最短转换序列的长度对应）
public class Solution {
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return a list of lists of string
*/
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
// write your code here
Map<String, List<String>> g = new HashMap<>();
Set<String> words = new HashSet<>(dict);
words.add(start);
words.add(end);
String[] wordArray = words.toArray(new String[0]);
for (int i = 0; i < wordArray.length - 1; ++i) {
for (int j = i + 1; j < wordArray.length; ++j) {
String first = wordArray[i], second = wordArray[j];
if (this.wordDiffCnt(first, second) == 1) {
if (!g.containsKey(first)) {
List<String> newList = new ArrayList<>();
g.put(first, newList);
}
g.get(first).add(second);
if (!g.containsKey(second)) {
List<String> newList = new ArrayList<>();
g.put(second, newList);
}
g.get(second).add(first);
}
}
}
resultMap = new HashMap<>();
visit = new HashSet<>();
// return dfs(g, start, end);//超时了，不知道怎么优化
List<List<String>> result = new ArrayList<>();
dist = new HashMap<>();
dfs(result, new LinkedList<String>(), g, start, end, bfs(g, end, start));
return result;
}
//通过bfs计算 终结点 到 源结点 的最短转换长度，以及 终结点到各个结点的最短距离（在通过 dfs寻找 最短转换序列的时候用到）
private Map<String, Integer> dist;
private int bfs(Map<String, List<String>> g, String start, String end) {
Queue<String> queue = new LinkedList<>();
visit.add(start);
queue.add(start);
dist.put(start, 1);
int minLen = 0;
while(!queue.isEmpty()) {
start = queue.poll();
if(start.equals(end)) {
if(minLen == 0) {
minLen = dist.get(start);
}
}
if(g.containsKey(start)) {
for (String next : g.get(start)) {
if(visit.contains(next)) continue;
visit.add(next);
queue.add(next);
dist.put(next, dist.get(start)+1);
}
}
}
visit.clear();
return minLen;
}
private void dfs(List<List<String>> result, List<String> tmp, Map<String, List<String>> g, String start, String end, int minLen) {
if(tmp.size()+dist.get(start)-1 >= minLen) return;
if (start.equals(end)) {
result.add(new ArrayList<>(tmp));
result.get(result.size() - 1).add(end);
return;
}
visit.add(start);
tmp.add(start);
if (g.containsKey(start)) {
for (String next : g.get(start)) {
if(visit.contains(next)) continue;
dfs(result, tmp, g, next, end, minLen);
}
}
visit.remove(start);
tmp.remove(tmp.size()-1);
}
@Deprecated
private List<List<String>> dfs(Map<String, List<String>> g, String start, String end) {
List<List<String>> result = new ArrayList<>();
if (start.equals(end)) {
List<String> list = new ArrayList<>();
list.add(end);
result.add(list);
resultMap.put(end, result);
return result;
}
if (resultMap.containsKey(start)) {
return resultMap.get(start);
}
if (!g.containsKey(start)) {
resultMap.put(start, null);
return null;
}
visit.add(start);
List<List<String>> nextResult = new ArrayList<>();
int minLen = Integer.MAX_VALUE;
for (String next : g.get(start)) {
if(visit.contains(next)) continue;
List<List<String>> tmp = dfs(g, next, end);
if (tmp != null) {
for (List<String> list : tmp) {
if(minLen > list.size()) minLen = list.size();
nextResult.add(list);
}
}
}
visit.remove(start);
for (List<String> list : nextResult) {
if (list.size() == minLen) {
List<String> tmp = new LinkedList<>(list);
tmp.add(0, start);
result.add(tmp);
}
}
if(result.size() > 0) {
resultMap.put(start, result);
}
return result;
}
//记忆化搜索 每个节点到终点的最小步数的路径
private Map<String, List<List<String>>> resultMap;
//每个节点的访问的情况
private Set<String> visit;
private int wordDiffCnt(String s1, String s2) {
int diffCnt = 0;
for (int i = 0; i < s1.length(); ++i) {
if (s1.charAt(i) != s2.charAt(i)) {
++diffCnt;
}
}
return diffCnt;
}
}
