题意
给出两个单词（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; } }
