首页 > 代码库 > Word Ladder II

Word Ladder II

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

  1. Only one letter can be changed at a time
  2. 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.

用了一天的时间终于把它AC掉了,不容易啊,太难了,也证明了自己的能力还是不行。总结一下这道题的思路:

基本的思路依然延续Word Ladder的思想,用‘a’~‘z’替换字符串中的每一个值来判断字符串和字典中字符串之间的关系,如果一次替换后的字符串出现字典中,那么说明这个字符串和替换后对应字典中字符串之间的距离为1,这样就节省了创建邻接矩阵的时间,这个还是一个很不错的想法。

其次就是本题的特色了,不仅要求出ladder的长度,还要知道ladder的每一阶是什么,也就是记录下搜索路径。记录搜索路径的话就是DFS了。如何知道路径呢,那么就要创建搜索树。如何创建搜索树呢?按照传统的BFS的思路,访问一个节点就将这个节点设置为visited的,那么当所有的节点都visited之后,这颗树就成了,那么是否有问题呢?用图说明问题


技术分享

是否观察到区别?

传统的BFS搜索的节点只有一个确定的父节点,而我们需要的搜索树会出现多个父节点因此,传统的BFS的改良,我们使用两个队列来记录访问的过程,一个就是传统BFS算法所用的队列queue,然后这里还要使用一个额外的队列LevelElements,这个队列就是从上一层得到的下一层的元素,可以重复,如第二层是ted,rex,那么访问过这一层之后得到的LevelElements就是[tad,tex,tex],然后去重加入queue中。这就是改进的搜索树。

至于树节点之间的关系,我们使用一个map,记录访问到的每一个节点和节点的parent节点。

DFS过程中,由于已经有了每一个节点的parent节点,那么搜索树的形状就知道了,所以用DFS就可以得到所有的路径。至于路径的保存问题,我们使用一个LinkedList 类型tmp列表,搜索到一个节点,就将它加入tmp,离开它的时候从tmp中移除。这样当搜索到start的时候tmp就是一个完整的路径了,然后深度copy tmp,加入总路径记录的list中。

至此,整个算法思想介绍完毕了,算法是自己一边度娘一边自己写,花费的时间虽然很多,但是还是很高兴的,终于AC过了。

这道题DFS和BFS结合的还是很完美的。

public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> dict) { 
        List<List<String>> list = new LinkedList<List<String>>();
        //特殊情况
        if (start == null || end == null)  
            return list;  
        if (isOneWordDiff(start, end)){
           List<String>  l = new ArrayList<String>();
           l.add(start);
           l.add(end);
           list.add(l);
           return list;
        }  
        
        dict.add(start);//即使字典已经包含start和end也无所谓
        dict.add(end);
        
        /*********主要涉及的数据结构***********/
        Queue<String> queue = new LinkedList<String>();//访问队列,用来记录访问的顺序,里面可能存在了多层的元素
	Queue<String> levelElements = new LinkedList<String>();//记录通过上层可以访问到的所有的元素,可能会有重复,这个队列只保存一层里的数据,不会保存多层元素
        Map<String,Set<String>> parent = new HashMap<String,Set<String>>();//使用map记录访问节点和访问节点的父节点,由于有可能有多个parent所以使用Set来存储
	Set<String> visited = new HashSet<String>();
        /************************************************/
        //List<String> parent = new ArrayList<String>();//存储end的parent
        StringBuilder sb = null;//重复修改字符串并且是单线程使用StringBuilder
        int level = 0;//某一层的元素数
        //int len = 0;
        queue.offer(start);
	visited.add(start);
        level++;
        parent.put(start,new HashSet<String>());//start的parent为""
        Set<String> parentSet = null;
        //parentSet.add("");
	//System.out.println(parent);
        boolean flag = false;//找到了end所在的len层,那么当len层的所有元素都出队之后就可以结束了
        while(!queue.isEmpty())  
        {  
            //len++;
            int count = 0;
            //int nextLevel = 0;
            while(count < level){//控制出队的个数,len层出队
                String tmp = queue.poll();
                if(end.equals(tmp)){//找到了end,如果找到了end,说明end的parent已经存到了map里,因此可以退出循环,而不用管是否队空
                    flag = true;
                    break;
                }else{
                    //将能够进行一次转换就到字典里的string加到队列,也就是离tmp最近的
                    sb = new StringBuilder(tmp);//重复修改字符串并且是单线程使用StringBuilder
                    for(int i = 0 ; i < tmp.length(); i++){
                        char c = sb.charAt(i);
                        //parentSet = parent.get(tmp);
                        for(char j = 'a' ; j <= 'z' ; j ++){
                            if(j == c){
                                continue;
                            }else{
                                sb.setCharAt(i,j);
                                if(dict.contains(sb.toString()) && !visited.contains(sb.toString())){       
		     			levelElements.offer(sb.toString());			
                                        if(parent.containsKey(sb.toString())){
                                            parentSet = parent.get(sb.toString());
                                            parentSet.add(tmp);
                                        }else{
                                            //queue.offer(sb.toString());                   
                                            parentSet = new HashSet<String>();
                                            parentSet.add(tmp);
                                            parent.put(sb.toString(),parentSet);   
                                        }
                                }
                            }
                        }
                        sb.setCharAt(i,c);
                    }
                }
                count++;
            }
	    if(flag){
                break;
            }
	    level = 0;
	    //System.out.println(levelElements); 
	    while(!levelElements.isEmpty()){
	    	String tmp = levelElements.poll();
		if(!visited.contains(tmp)){
			queue.offer(tmp);
			level++;
			visited.add(tmp);
		}
	    }
	    //System.out.println(queue); 
	    //break;
        }
        if(!parent.containsKey(end)){
            return list;
        }
	//System.out.println(parent);
        List<String> tmp = new LinkedList<String>();//用来构造路径
        buildPath(list,tmp,parent,start,end);
        return list;
    }
    private boolean isOneWordDiff(String a, String b) {  
        int diff = 0;  
        for (int i = 0; i < a.length(); i++) {  
            if (a.charAt(i) != b.charAt(i)) {  
                diff++;  
                if (diff >= 2)  
                    break;  
            }  
        }  
        return diff == 1;  
    }
    public void buildPath(List<List<String>> list,List<String> tmp,Map<String,Set<String>> parent,String start,String s){
        if(s.equals(start)){
		tmp.add(0,s);
                List<String> l = new LinkedList<String>();
                for(int i = 0; i < tmp.size(); i ++){//深度复制
                    l.add(tmp.get(i));
                }
		//l.add(0,start);
                list.add(l);
		tmp.remove(s);
	}
	Set<String> set = parent.get(s);//获得s的父亲
        for(String s1: set){
                tmp.add(0,s);
                buildPath(list,tmp,parent,start,s1);
                tmp.remove(s);
        }
    }
}

技术分享


Runtime: 888 ms

这个运行时间挺不错的,提交了多次得到了这个时间技术分享,时间不一定,有时候能到700多ms。

自己的测试代码

import java.util.*;
public class Solution {
    public static void main(String[] args){
    	Solution solution = new Solution();
	String start = "qa";
	String end = "sq";
	String[] s = {"si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye"};
	Set<String> dict = new HashSet<String>();
	for(int i = 0 ; i < s.length; i ++){
		dict.add(s[i]);
	}
	//System.out.println(solution.findLadders(start,end,dict));
	solution.findLadders(start,end,dict);
	//System.out.println(dict);
    }
    public List<List<String>> findLadders(String start, String end, Set<String> dict) { 
        List<List<String>> list = new LinkedList<List<String>>();
        //特殊情况
        if (start == null || end == null)  
            return list;  
        if (isOneWordDiff(start, end)){
           List<String>  l = new ArrayList<String>();
           l.add(start);
           l.add(end);
           list.add(l);
           return list;
        }  
        
        dict.add(start);//即使字典已经包含start和end也无所谓
        dict.add(end);
        
        /*********主要涉及的数据结构***********/
        Queue<String> queue = new LinkedList<String>();//访问队列,用来记录访问的顺序,里面可能存在了多层的元素
	Queue<String> levelElements = new LinkedList<String>();//记录通过上层可以访问到的所有的元素,可能会有重复,这个队列只保存一层里的数据,不会保存多层元素
        Map<String,Set<String>> parent = new HashMap<String,Set<String>>();//使用map记录访问节点和访问节点的父节点,由于有可能有多个parent所以使用Set来存储
	Set<String> visited = new HashSet<String>();
        /************************************************/
        //List<String> parent = new ArrayList<String>();//存储end的parent
        StringBuilder sb = null;//重复修改字符串并且是单线程使用StringBuilder
        int level = 0;//某一层的元素数
        //int len = 0;
        queue.offer(start);
	visited.add(start);
        level++;
        parent.put(start,new HashSet<String>());//start的parent为""
        Set<String> parentSet = null;
        //parentSet.add("");
	//System.out.println(parent);
        boolean flag = false;//找到了end所在的len层,那么当len层的所有元素都出队之后就可以结束了
        while(!queue.isEmpty())  
        {  
            //len++;
            int count = 0;
            //int nextLevel = 0;
            while(count < level){//控制出队的个数,len层出队
                String tmp = queue.poll();
                if(end.equals(tmp)){//找到了end,如果找到了end,说明end的parent已经存到了map里,因此可以退出循环,而不用管是否队空
                    flag = true;
                    break;
                }else{
                    //将能够进行一次转换就到字典里的string加到队列,也就是离tmp最近的
                    sb = new StringBuilder(tmp);//重复修改字符串并且是单线程使用StringBuilder
                    for(int i = 0 ; i < tmp.length(); i++){
                        char c = sb.charAt(i);
                        //parentSet = parent.get(tmp);
                        for(char j = 'a' ; j <= 'z' ; j ++){
                            if(j == c){
                                continue;
                            }else{
                                sb.setCharAt(i,j);
                                if(dict.contains(sb.toString()) && !visited.contains(sb.toString())){       
		     			levelElements.offer(sb.toString());			
                                        if(parent.containsKey(sb.toString())){
                                            parentSet = parent.get(sb.toString());
                                            parentSet.add(tmp);
                                        }else{
                                            //queue.offer(sb.toString());                   
                                            parentSet = new HashSet<String>();
                                            parentSet.add(tmp);
                                            parent.put(sb.toString(),parentSet);   
                                        }
                                }
                            }
                        }
                        sb.setCharAt(i,c);
                    }
                }
                count++;
            }
	    if(flag){
                break;
            }
	    level = 0;
	    //System.out.println(levelElements); 
	    while(!levelElements.isEmpty()){
	    	String tmp = levelElements.poll();
		if(!visited.contains(tmp)){
			queue.offer(tmp);
			level++;
			visited.add(tmp);
		}
	    }
	    //System.out.println(queue); 
	    //break;
        }
        if(!parent.containsKey(end)){
            return list;
        }
	//System.out.println(parent);
        List<String> tmp = new LinkedList<String>();//用来构造路径
        buildPath(list,tmp,parent,start,end);
        return list;
    }
    private boolean isOneWordDiff(String a, String b) {  
        int diff = 0;  
        for (int i = 0; i < a.length(); i++) {  
            if (a.charAt(i) != b.charAt(i)) {  
                diff++;  
                if (diff >= 2)  
                    break;  
            }  
        }  
        return diff == 1;  
    }
    public void buildPath(List<List<String>> list,List<String> tmp,Map<String,Set<String>> parent,String start,String s){
        if(s.equals(start)){
		tmp.add(0,s);
                List<String> l = new LinkedList<String>();
                for(int i = 0; i < tmp.size(); i ++){//深度复制
                    l.add(tmp.get(i));
                }
		//l.add(0,start);
                list.add(l);
		tmp.remove(s);
	}
	Set<String> set = parent.get(s);//获得s的父亲
        for(String s1: set){
                tmp.add(0,s);
                buildPath(list,tmp,parent,start,s1);
                tmp.remove(s);
        }
    }
}

技术分享

一共是51组




Word Ladder II