注意事项

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;    }}