126. Word Ladder II

题目：

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

Only one letter can be changed at a time
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"]

  ]

Note:

All words have the same length.
All words contain only lowercase alphabetic characters.

链接： https//leetcode.com/problems/word-ladder-ii/

题解：

求所有最短路径...第一想法是先定义一个用adjacent list表示的图类，然后用Dijkstra求最短路径们。

再仔细想一想，我们现在应该有两条路，一条是在Word Ladder I的基础上改进，另外一条是用一个不太一样的方法从头思考设计和解决。

先试试第一条，在Word Ladder I基础上改进。一个可能的解法基本步骤可能是:

1. 按照Word Ladder I的方法，用BFS求最段路径
2. 找到第一条最短路径的时候，不返回，继续计算Queue里这一层BFS其他结点，看是否能有其他最短路径。因为在这一层找到了最短路径，所以长度是固定的，找完这一层就可以结束了，返回结果。
3. 在每一层BFS的时候cache之前路径。对于 visited的处理，在每一层运算结束之后再统一更新visited，否则如果下一节点由这一层的多个节点共用，会出问题。　　
4. 如何保存已经访问过的节点。比如假设用 HashMap<String, List<String>>来保存下一节点与之前路径，假设有一条为 tex, {red，ted，tex}，还有一条 tex，{red，rex，tex}，这时就有了collision。所以可能只能储存前序的节点，并不能保存整个路径，除非额外做些处理，比如另外做数据结构，或者把路径做成 word + delimiter，然后比较的时候取split string得到的数组里的最后一个元素，之类的。　　　
5. 只存前序节点的话，最后的结果应该是在HashMap里的一条<endWord, List<String>>。这样再从endWord开始对List<String>做一个DFS，应该就可以找到所要求的路径。

12:53AM，尝试完毕，可以作为一个解。要继续研究最优解法。终于AC了好高兴，基本算是做了整整一天。写的代码丑陋异常...一定要再优化优化。复杂度应该和1一样，不过代码里面用到了list的contains，也许会增加一些低阶量。

Time Complexity - O(min(26^L, size(wordList))， Space Complexity - O(min(26^L, size(wordList))， L为 word length。

public class Solution {

    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {

        List<List<String>> res = new ArrayList<>();

        if(beginWord == null || endWord == null || wordList == null || wordList.size() == 0 || beginWord.equals(endWord))

            return res;

        if(wordList.contains(beginWord))

            wordList.remove(beginWord);

        if(wordList.contains(endWord))

            wordList.remove(endWord);

        Queue<String> q = new LinkedList<>();

        q.offer(beginWord);

        int curLevel = 1, nextLevel = 0;

        HashSet<String> visited = new HashSet<>();

        HashSet<String> levelVisited = new HashSet<>();

        HashMap<String, ArrayList<String>> wordChains = new HashMap<>();

        boolean foundShortestPath = false;

        while(!q.isEmpty()) {

            String word = q.poll();

            curLevel--;

            for(int i = 0; i < word.length(); i++) {

                char[] wordAsArray = word.toCharArray();

                for(char j = 'a'; j <= 'z'; j++) {

                    wordAsArray[i] = j;

                    String newWord = String.valueOf(wordAsArray);

                    if(newWord.equals(endWord)) {               // found shortest path at this level

                        foundShortestPath = true;               // flag to only process this level, then return

                        if(wordChains.containsKey(endWord)) {

                            if(!wordChains.get(endWord).contains(word))

                                wordChains.get(endWord).add(word);

                        } else {

                            ArrayList<String> preWords = new ArrayList<>();

                            preWords.add(word);

                            wordChains.put(endWord, preWords);

                        }

                        break;

                    }

                    if(wordList.contains(newWord) && !visited.contains(newWord)) {  //found edge to next node

                        q.offer(newWord);

                        if(wordChains.containsKey(newWord)) {

                            if(!wordChains.get(newWord).contains(word))

                                wordChains.get(newWord).add(word);

                        } else {

                             ArrayList<String> preWords = new ArrayList<>();

                             preWords.add(word);

                             wordChains.put(newWord, preWords);

                        }

                        nextLevel++;

                        levelVisited.add(newWord);              //add the newWord to a temp visited HashMap

                    }

                }

            }

            if(curLevel == 0) {

                if(foundShortestPath)

                    break;

                curLevel = nextLevel;

                nextLevel = 0;

                for(String str : levelVisited)               //update the global "visited"

                    visited.add(str);

                levelVisited.clear();

            }

        }

        ArrayList<String> list = new ArrayList<>();

        list.add(endWord);

        getWordChains(res, list, wordChains, beginWord, endWord);

        return res;

    }

    private void getWordChains(List<List<String>> res, ArrayList<String> list, HashMap<String, ArrayList<String>> wordChains, String beginWord, String endWord) {

        if(endWord.equals(beginWord)) {

            res.add(new ArrayList<String>(list));

            return;

        }

        ArrayList<String> curLevel= new ArrayList<>();

        if(wordChains.containsKey(endWord))

            curLevel = wordChains.get(endWord);

        else

            return;

        for(int i = 0; i < curLevel.size(); i++) {

            String word = curLevel.get(i);

            list.add(0, word);

            getWordChains(res, list, wordChains, beginWord, word);

            list.remove(word);

        }

    }

}

再试试第二条(刷下一遍时)

急需学习图的各种知识。WordLadder这种经典题目，Sedgewick的算法书和Mark Ellen Weiss的数据结构书里都有涉及，要多学多练。

题外话：中午去SOHO和Justin谈了一下，他说有3个startup不错，一个是doubleclick前CEO做的，专门搞古董交易的startup。第二个是ADP sponsor的internal子公司，做得很像zenefits。第三个是一个做男士剃须刀的，有专门的厂家在德国，目标是在你需要刮胡子的时候快递新的刮胡刀上门。真的很有意思，broaden my vision。下午继续回公司做事，要处理好和同事，上级的关系，要有耐心，不要急躁。

Reference：

http://baike.baidu.com/view/349189.htm

https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98

http://blog.csdn.net/v_july_v/article/details/6181485

http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Graph.java.html

http://www.cnblogs.com/springfor/p/3893529.html

http://blog.csdn.net/linhuanmars/article/details/23071455

秒客网

126. Word Ladder II

相关文章