Word Ladder II 121

Question

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

Notice

All words have the same length.

All words contain only lowercase alphabetic characters.

Example

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

Return

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

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

]

Solution

求最短距离的所有解，利用BFS+DFS。

1) BFS过程与Word Ladder类似，但是在BFS过程中利用一个HashMap(distance)记录每个单词距start的最短距离，另一个HashMap(map)记录每个单词是由哪些单词变换一步得到的。

2) DFS过程类似Permutation，从end出发，逐个寻找其上一节点直到start。其中可能的上一节点可以由1）中的map得到，但是只有距离比当前节点距离小1的上一节点才是合法的（保证其一定在end和start之间的最短路径上，即找到的下一个点一定比当前点离start更近，这样防止搜到的下一个点向外走），距离可以由1）中的distance得到。当到达start时即找到一种解，因为是从end出发，所以要reverse成正序后再加入res，然后reverse回逆序后删除刚加入元素，再回溯寻找下一个解。

注意：在dfs获取next的list的时候，需要判断curt是否在map中，否则可能得到null而造成之后的运行时异常。比如start="hot"，end="dog"，dict={"hot", "dog"}，这里在bfs中就找不到hot和dog的next，因此没有元素会被加到map和distance中。在lintcode里可以过，但是在leetcode里过不了。

代码如下：

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
        List<List<String>> result = new ArrayList<List<String>>();
        if(dict == null){
            return result;
        }

        dict.add(start);
        dict.add(end);

        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        HashMap<String, Integer> distance = new HashMap<String, Integer>();
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        distance.put(start, 0);

        bfs(map, distance, queue, dict);

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

        dfs(result, list, end, start, distance, map);

        return result;
    }

    private void dfs(List<List<String>> result, List<String> list, String curt, String start, HashMap<String, Integer> distance, HashMap<String, ArrayList<String>> map){
        list.add(curt);
        if(curt.equals(start)){
            Collections.reverse(list);
            result.add(new ArrayList<String>(list));
            Collections.reverse(list);
        }else{
            if(map.containsKey(curt)){
                for(String next : map.get(curt)){
                    if(distance.containsKey(next) && distance.get(curt) == distance.get(next) + 1){
                        dfs(result, list, next, start, distance, map);
                    }
                }
            }
        }
        list.remove(list.size() - 1);
    }

    private void bfs(HashMap<String, ArrayList<String>> map, HashMap<String, Integer> distance, Queue<String> queue, Set<String> dict){
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                String curt = queue.poll();
                for(String next : expend(curt, dict)){
                    if(!map.containsKey(next)){
                        map.put(next, new ArrayList<String>());
                        map.get(next).add(curt);
                    }else{
                        map.get(next).add(curt);
                    }

                    if(!distance.containsKey(next)){
                        distance.put(next, distance.get(curt) + 1);
                        queue.offer(next);
                    }
                }
            }
        }
    }

    private ArrayList<String> expend(String word, Set<String> dict){
        ArrayList<String> nextWords = new ArrayList<String>();
        for(char c = 'a'; c <= 'z'; c++){
            for(int i = 0; i < word.length(); i++){
                if(c == word.charAt(i)){
                    continue;
                }
                String newWord = replace(word, i, c);
                if(dict.contains(newWord)){
                    nextWords.add(newWord);
                }
            }
        }
        return nextWords;
    }

    private String replace(String word, int index, char c){
        char[] charac = word.toCharArray();
        charac[index] = c;
        return new String(charac);
    }
}