lintcode 单词接龙II

样例

给出数据如下：

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;

    }

}