Word Ladder II

Leave a comment

November 21, 2016 by oneOokay

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"]
  ]

Note:

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

  1. 一个Map<String, Integer> distance用来存从start变化为该word到的距离:e.g. <start, 0>
  2. 一个Map<String, ArrayList<String>> parent用来存,这个word变换一次能构成的所有word
  3. BFS一次遍历建立起以上两个hashmap
  4. DFS + backtracing来找到符合条件的路径:注意这里的dfs和其他dfs不一样的地方
public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord,
 Set<String> wordList) {
        List<List<String>> ans = new ArrayList<>();
        if (wordList == null || wordList.size() == 0){
            return ans;
        }
        
        HashMap<String, ArrayList<String>> parent = new HashMap<>();
        HashMap<String, Integer> distance = new HashMap<>();
        //在wordList里面加入startWord和endWord,便于bfs的时候找到所有的parents
        wordList.add(startWord); //我觉得要加这个,有这个eclipse里面才能跑通不报错;
但是leetcode里面不加这个也跑的通,有点奇怪。       
        wordList.add(endWord);
        bfs(beginWord, endWord, wordList, parent, distance);
        dfs(beginWord, endWord, parent, distance, new ArrayList<String>(), ans);
        return ans;
    }
    
    private void bfs(String start, String end, Set<String> wordList, 
HashMap<String, ArrayList<String>> parent, HashMap<String, Integer> distance){
        
        for (String s : wordList){
            parent.put(s, new ArrayList<String>());//初始化parent hashmap,防止后面报错
        }
        
        Queue queue = new LinkedList();
        queue.offer(start);
        int curDistance = 0; //distance to startWord,其实这里0或者1无所谓,因为没有求路径长度。
//目前这里curDistance的作用仅在于用来+1以确认变换为1的两个单词。
        distance.put(start, curDistance);
        while (!queue.isEmpty()){
            int count = queue.size();//这里很妙;所以每一次while循环结束,
意味着该层循环结束了,剩下的queue里面的元素全部都是下一层的元素。
            boolean foundEnd = false;//这里用来标记是否找到了end
//如果找到了的话,应该在全部处理完该层元素之后break;
            for (int i = 0; i < count; i ++){
                String curWord = queue.poll();
                ArrayList<String> neighbours = getNeighbours(curWord, wordList); 
//find the neighbours of a word: 所有的neighbour都是不同的,因为wordList里面不含重复元素
                curDistance = distance.get(curWord); //当前word距start的distance
                for (String neighbour : neighbours){
                    if (!distance.containsKey(neighbour)){//如果distance不含当前的word,
说明这个word第一次出现,此时为从start到这个词的最短路径。这里的distance hashmap起到了WordLadderI里面的visited的作用。
                        distance.put(neighbour, curDistance + 1); //shortest length
                        //同时也要记得放到queue里面,所以queue里面只放不重复的值
                        queue.offer(neighbour);
                        if (neighbour.equals(end)){
                            foundEnd =  true;
                        }
                        parent.get(curWord).add(neighbour);//把这个第一次出现的词加入到parent map里面
                    }else {//这个词已经出现过了,那么当前的路线肯定不是最短的,所以不需要update distance map
                        //只需要考虑是否需要加入到parent里面
                        if (!parent.get(curWord).contains(neighbour)){
                            parent.get(curWord).add(neighbour);
                        }
                    }
                }
            }//end of for loop
            if (foundEnd){ //这个break要放在for-loop结束之后也就是处理完一层之后
                break;
            }
        }
    }
    //具体看WordLadder I 的注释
    private ArrayList getNeighbours(String word, Set dict){
        char[] chars = word.toCharArray();
        ArrayList ans = new ArrayList<>();
        for (int i = 0; i < chars.length; i ++){
            char tmpChar = chars[i];
            for (char c = 'a'; c <= 'z'; c ++){
                if (tmpChar == c){
                    continue;
                }
                chars[i] = c;
                String newStr = String.valueOf(chars);
                if (dict.contains(newStr)){
                    ans.add(newStr);
                }
            }
            chars[i] = tmpChar;
        }
        return ans;
    }
    //这个dfs和之前的dfs有一些不同:之前的dfs是在for-loop中进行增加和移除的操作,
且在一开始直接进行条件判断的。而这里dfs是在整个method中进行增加移除,先把current加入到tmpList中,之后再进行条件判断。
    private void dfs(String current, String end, 
HashMap<String, ArrayList> parent, HashMap<String, Integer> distance, 
List tmpList, List<List> ans){
        tmpList.add(current);
        if (current.equals(end)){
            ans.add(new ArrayList<>(tmpList));//而且这里并不return,因为在最后要把新加入的元素移除
        }else {
                ArrayList neighbours = parent.get(current);
                for (String neighbour : neighbours){
                    //如果当前的neighbour是由current进行一步变换而来的,那么继续dfs
                    if (distance.get(neighbour) == distance.get(current) + 1){
                        dfs(neighbour, end, parent, distance, tmpList, ans);    
                    }
                }
        }
        tmpList.remove(tmpList.size() - 1);
    }
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: