Word Ladder Series

Word Ladder

Question

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,

return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Analysis

所有的词可以构成一张图，每个词相当于一个顶点，彼此间相差一个字母的词相连，利用BFS遍历整张图，第一次碰到endWord时的距离即使最短的。

• 由于正常查找toAdd的方式会TLE，所以在每次得到toAdd的时候，将较小的集合作为begin，较大的集合作为end
• 题中给出的List查找效率较低（我也不知道什么效率低，大概是查找吧），所以也会导致TLE，在一开始的时候就要创建Set

Code

Normal Solution

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord))  return 0;
        Set<String> reached=new HashSet<String>();
        reached.add(beginWord);
        int distance=1;
        
        while(!reached.contains(endWord)){
            Set<String> toAdd=new HashSet<String>();
            for(String each:reached){
                char[] str=each.toCharArray();
                for(int i=0;i<each.length();i++){
                    char old=str[i];
                    for(char c='a';c<='z';c++){
                        str[i]=c;
                        String newword=new String(str);
                        if(wordList.contains(newword)){
                            toAdd.add(newword);
                            wordList.remove(newword);
                        }
                    }
                    str[i]=old;
                }
            }
            distance++;
            if(toAdd.size()==0) return 0;
            reached=toAdd;
        }
        
        return distance;
    }
}

Two-end Solution

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordAsList) {
        if(!wordAsList.contains(endWord))  return 0;
        Set<String> wordList=new HashSet(wordAsList);
        Set<String> begin=new HashSet<String>();
        Set<String> end=new HashSet<String>();
        int distance=1;
        
        begin.add(beginWord);
        end.add(endWord);
        wordList.remove(beginWord);
        wordList.remove(endWord);
        
        while(!begin.isEmpty()){
            Set<String> toAdd=new HashSet<String>();
            for(String each:begin){
                char[] str=each.toCharArray();
                for(int i=0;i<each.length();i++){
                    char old=str[i];
                    for(char c='a';c<='z';c++){
                        str[i]=c;
                        String newword=String.valueOf(str);
                        
                        if(end.contains(newword))   return distance+1;
                        
                        if(wordList.contains(newword)){
                            wordList.remove(newword);
                            toAdd.add(newword);
                        }
                    }
                    str[i]=old;
                }
            }
            begin=(toAdd.size()<end.size())?toAdd:end;
            end=(begin.size()<end.size())?end:toAdd;
            distance++;
        }
        
        return 0;
    }
}

Word Ladder II

Question

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 transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Return

[

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

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

]

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Analysis

LeetCode Discussion

• 利用BFS，找到所有词间可能的关系，利用DFS，找到相应的路径并添加到res中
• BFS遍历过程同Word Ladder I，只不过不需要再找到endWord时候退出循环
• nodeneighbors 保存每个节点的邻居节点
• distance 保存当前节点与beginWord相差的字母个数，只有在BFS过程中第一次遇到某词才进行添加，后续不需要更新，因为第一次碰到是距离beginWord距离最短的
• DFS遍历过程中同Backtracking，在每次调用初始像solution加入当前节点，在碰到endWord时，向res加入solution，加入solution时需要new ArrayList\(Solution)
• DFS过程中，当下一节点与当前节点距离beginWord距离相差1时递归调用，且在完成一次递归调用的时候，删除在此次调用时加入的节点

Code

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordAsList) {
        List<List<String>> res=new ArrayList();
        if(!wordAsList.contains(endWord))   return res;
        List<String> solution=new ArrayList();
        Map<String, ArrayList<String>> neighbors=new HashMap();
        Map<String,Integer> distance=new HashMap();
        Set<String> wordList=new HashSet(wordAsList);
        wordList.add(beginWord);
        distance.put(beginWord,0);
        
        bfs(beginWord,endWord,wordList,neighbors,distance);
        dfs(beginWord,endWord,wordList,neighbors,distance,solution,res);
        
        return res;
    }
    
    private void bfs(String beginWord, String endWord, Set<String> wordList, Map<String,ArrayList<String>> nodeneighbors, Map<String,Integer> distance)
    {
        for(String word:wordList){
            nodeneighbors.put(word,new ArrayList<String>());
        }
        
        List<String> begin=new ArrayList();
        begin.add(beginWord);
        distance.put(beginWord,0);
        
        while(!begin.isEmpty()){
            List<String> toAdd=new ArrayList();
            boolean findend=false;
        
            for(String each:begin){
                
                int curdistance=distance.get(each);
                List<String> neighbors=getneighbors(each,wordList);
                
                for(String item:neighbors){
                    nodeneighbors.get(each).add(item);
                    if(!distance.containsKey(item)){
                        distance.put(item,curdistance+1);
                        toAdd.add(item);
                    }
                }
            }
            begin=toAdd;
        }
    }
    
    private List<String> getneighbors(String str, Set<String> wordList){
        List<String> neighbors=new ArrayList();
        char[] s=str.toCharArray();
        
        for(int i=0;i<s.length;i++){
            char old=s[i];
            for(char c='a';c<='z';c++){
                if(s[i]==c)     continue;
                s[i]=c;
                String newWord=new String(s);
                
                if(wordList.contains(newWord)){
                    neighbors.add(newWord);
                }
            }
            s[i]=old;
        }
        
        return neighbors;
    }
    
    private void dfs(String cur, String endWord, Set<String> wordList, Map<String,ArrayList<String>> nodeneighbors, Map<String,Integer> distance, List<String> solution, List<List<String>> res){
        
        solution.add(cur);
        if(cur.equals(endWord)){
            res.add(new ArrayList<String>(solution));
        }
        else{
            for(String next:nodeneighbors.get(cur)){
                if(distance.get(next)==distance.get(cur)+1){
                    dfs(next,endWord,wordList,nodeneighbors,distance,solution,res);
                }
            }   
        }
        solution.remove(solution.size()-1);
    }
}