Leetcode - Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = "hit"
end = "cog"
dict = ["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.

[分析] 这是一道呼唤耐心的题目，基本思路和word ladder一致，利用BFS搜索出最短路径，所不同的是这题需要找出所有最短路径，因此在搜索时需要记录搜索路径以便于最后进行回溯。有几个关键的细节需要注意：
1）搜索到一个可供跳转的单词时不能像word ladder题中那样立即删除，需要遍历完当前层后再统一从dict中删除下一层的单词，考虑这种情况：input= {"bet", "hat", ["bet", "bit", "bot", "hit", "hot", "hat"]},遍历第三层hit时，若直接删除hat，则最终output会少一条从hot到hat的路径。遍历每层时使用visited集合记录所有下一层单词，该层遍历结束后从dict中删除该层对应的visited集合。
2）反方向搜索，即从end往start搜，可提高回溯时的效率，因为构造路径时可顺序添加而无需插入在数组头部（会有隐藏的数组移位操作）。
3）为了方便回溯，反向搜索过程中要记录当前元素的前驱（output路径方向看），可使用HashMap,key为当前元素，value是key的前驱列表。正向搜索记录后继也是可行的，但实现起来会麻烦些，因为在遍历过程中找到的后继不一定最终能导向end，在回溯时需要进行额外判断，不然可能会空指针。
4) 忽略if (visited.add(newStr))这个条件直接queue.offer(newStr)会导致超时，因为queue中会加入重复元素

先参照http://blog.csdn.net/linhuanmars/article/details/23071455 稍微修改了如Method1所示，然后再此基础上修改了自己初始的想法得到Method 2实现

[ref]
http://www.cnblogs.com/TenosDoIt/p/3443512.html
http://blog.csdn.net/linhuanmars/article/details/23071455
http://blog.csdn.net/u013325815/article/details/42043051

// Method 2: 去除Method1 的辅助数据结构
public class Solution1 {   
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> result = new ArrayList<List<String>>();
        LinkedList<String> queue = new LinkedList<String>();
        queue.add(end);
        HashMap<String, ArrayList<String>> nextMap = new HashMap<String, ArrayList<String>>();
        HashSet<String> visited = new HashSet<String>();
        dict.add(start);
        dict.remove(end);
        int currLevel = 1, nextLevel = 0;
        int L = start.length();
        boolean found = false;
        while (!queue.isEmpty()) {
            String currStr = queue.poll();
            if (currLevel == 0) {
                if (found) break;
                currLevel = nextLevel;
                nextLevel = 0;
                dict.removeAll(visited);
                visited.clear();
            }
            char[] currCharArray = currStr.toCharArray();
            for (int i = 0; i < L; i++) {
                char oldChar = currCharArray[i];
                boolean foundCurCycle = false;
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == oldChar) continue;
                    currCharArray[i] = c;
                    String newStr = new String(currCharArray);
                    if (dict.contains(newStr)) {
                        if (!nextMap.containsKey(newStr)) {
                            nextMap.put(newStr, new ArrayList<String>());
                        }
                        nextMap.get(newStr).add(currStr);
                        // 务必先更新nextMap再判断搜索是否结束，否则nextMap可能最终为空
                        if (newStr.equals(start)) {
                            found = true;
                            foundCurCycle = true;
                            break;
                        }
                        if (visited.add(newStr)) {
                            queue.offer(newStr);
                            nextLevel++;
                        }
                    }
                }
                currCharArray[i] = oldChar;
                if (foundCurCycle) break;
            }
            currLevel--;
        }
        if (found) {
            List<String> item = new ArrayList<String>();
            item.add(start);
            getPath(start, end, item, nextMap, result);
        }
        return result;
    }
    
    public void getPath(String start, String end, List<String> item, 
        HashMap<String, ArrayList<String>> nextMap, List<List<String>> result) {
        if (start.equals(end)) {
            result.add(new ArrayList<String>(item));
        } else {
            ArrayList<String> nextList = nextMap.get(start);
            for (String next : nextList) {
                item.add(next);
                getPath(next, end, item, nextMap, result);
                item.remove(item.size() - 1);
            }
        }
    }
}

// Method 1, 参考下面链接修改
// http://blog.csdn.net/linhuanmars/article/details/23071455
public class Solution {
    class StringWithLevel {
        String str;
        int level;
        public StringWithLevel(String str, int level) {
            this.str = str;
            this.level = level;
        }
    }
    
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> result = new ArrayList<List<String>>();
        LinkedList<StringWithLevel> queue = new LinkedList<StringWithLevel>();
        queue.add(new StringWithLevel(end, 0));
        HashMap<String, ArrayList<String>> nextMap = new HashMap<String, ArrayList<String>>();
        HashSet<String> visited = new HashSet<String>();
        dict.add(start);
        dict.remove(end);
        int currLevel = 0, preLevel = 0;
        int L = start.length();
        boolean found = false;
        while (!queue.isEmpty()) {
            StringWithLevel curr = queue.poll();
            String currStr = curr.str;
            currLevel = curr.level;
            if (currLevel > preLevel) {
                if (found) break;
                preLevel = currLevel;
                dict.removeAll(visited);
                visited.clear();
            }
            char[] currCharArray = currStr.toCharArray();
            for (int i = 0; i < L; i++) {
                char oldChar = currCharArray[i];
                boolean foundCurCycle = false;
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == oldChar) continue;
                    currCharArray[i] = c;
                    String newStr = new String(currCharArray);
                    if (dict.contains(newStr)) {
                        ArrayList<String> nextList = null;
                        if (nextMap.containsKey(newStr)) {
                            nextList = nextMap.get(newStr);
                        } else {
                            nextList = new ArrayList<String>();
                        }
                        nextList.add(currStr);
                        nextMap.put(newStr, nextList);
                        if (newStr.equals(start)) {
                            found = true;
                            foundCurCycle = true;
                            break;
                        }
                        if (visited.add(newStr))
                            queue.offer(new StringWithLevel(newStr, currLevel + 1)); // enqueue a new item of next level
                    }
                }
                currCharArray[i] = oldChar;
                if (foundCurCycle) break; // can not use found here, or will miss some paths
            }
        }
        if (found) {
            List<String> item = new ArrayList<String>();
            item.add(start);
            getPath(start, end, item, nextMap, result);
        }
        return result;
    }
    
    public void getPath(String start, String end, List<String> item, 
        HashMap<String, ArrayList<String>> nextMap, List<List<String>> result) {
        if (start.equals(end)) {
            result.add(new ArrayList<String>(item));
        } else {
            ArrayList<String> nextList = nextMap.get(start);
            for (String next : nextList) {
                item.add(next);
                getPath(next, end, item, nextMap, result);
                item.remove(item.size() - 1);
            }
        }
    }
}