leetcode-Word Ladder II

2016-07-26 21:09:00

题目：
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1.Only one letter can be changed at a time
2.Each intermediate word must exist in the word list

For example,

Given:

beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]

Return
[

["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]

]

分析：
第一感觉是dfs + backtracking，就是先用bfs求出beginWord到endWord的最短距离，然后dfs + backtracking找到不同的路径，等于这个最短距离的留下，大于的pass，果断TLE。
简单思考了下，除了可能出现环的情况会TLE外，还可以通过剪枝的方法优化——用HashMap记录每个单词和beginWord之间的距离，当dfs遍历到某个单词已经比最短距离长的时候，就不用再遍历下去了。提交，又TLE。
仔细又一想，这种剪枝等于没剪枝，想想HashMap是怎么求出来的？是在BFS的时候层序更新的，搜索到endWord的时候就停止了。所以道理上不存在比到endWord更长的一条路。问题不是出在走了更长的路，而是因为所有的路线都是从beginWword辐射出去的，dfs搜索的话有太多的岔路。
所以一个比较自然的想法是，从endWord往回找，就可以避免许多岔路。进一步的剪枝是依据HashMap里记录的距离，规定dfs的方向只往里beginWord距离更小的方向遍历。
code:

import java.io.*;import java.util.*;public class WordLadderII {    public List> findLadders(String beginWord, String endWord, Set wordDict){        List> Ladders = new ArrayList>();        //优化一：BFS时记录每个单词的前驱        HashMap> preGraph = new HashMap>();        //优化二：记录每个节点的最短距离，往回找的时候可以进一步剪枝，同时在构图的过程中也避免了环的存在        HashMap distance = new HashMap();        wordDict.add(beginWord);        wordDict.add(endWord);        for(String word : wordDict){            preGraph.put(word, new ArrayList());        }        //build the graph, get the preGraph and distance        bfs(preGraph, distance, beginWord, wordDict);        //find all the shortest path        //List path = new ArrayList();        dfs(Ladders, new ArrayList(), endWord, beginWord, distance, preGraph);        return Ladders;    }    /*     *寻找差异为一的单词有两种方法：     *(1)将目标单词与字典里的所有单词比较，O(n*l), n是字典容量(1000+),l是单词长度；     *(2)将目标的字母用'a'-'z'挨个替换，利用Set.contains()函数搜索。由于Set.contains()是O(1)的，这种方法是O(26*l)      */    public List getNextWords(String words, Set wordDict){        List nextWords = new ArrayList();        for(int i = 0; i > preGraph, HashMap distance, String beginWord, Set wordDict){        LinkedList queue = new LinkedList();        queue.offer(beginWord);        distance.put(beginWord, 0);        while(!queue.isEmpty()){            String curr = queue.poll();            for(String next : getNextWords(curr, wordDict)){                preGraph.get(next).add(curr);                if(!distance.containsKey(next)){                    distance.put(next, distance.get(curr) + 1);                    //保证每个单词之进入队列一次                    queue.offer(next);                }            }        }    }    public void dfs(List> Ladders, List path, String curr, String beginWord, HashMap distance, HashMap> preGraph){        if(curr.equals(beginWord)){            path.add(curr);            Collections.reverse(path);            Ladders.add(path);            //Collections.reverse(path)            //path.remove(path.size() - 1)            return;        }        for(String next : preGraph.get(curr)){            //剪枝，去掉非最短路的情况            if(distance.get(curr) - 1 == distance.get(next)){                path.add(curr);                //如果这里直接用path而不是new ArrayList(path), 68行的代码就需要执行了                dfs(Ladders, new ArrayList(path), next, beginWord, distance, preGraph);                path.remove(path.size() - 1);            }        }    }    public static void main(String[] args){        Set dict = new HashSet();        dict.add("hot");        dict.add("dot");        dict.add("dog");        dict.add("lot");        dict.add("log");        WordLadderII WL = new WordLadderII();        List> ladders = WL.findLadders("hit","cog",dict);        for(List list : ladders){            System.out.println(list);        }    }}

时间复杂度方面：
(1)bfs构图的过程中，每个点进入队列一次，时间是O(n);
(2)dfs找路线的时候最坏情况是O(n^2),平均时间复杂度是O(n).

关键字：产品经理

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击举报进行投诉反馈！