Share two similar Java solution that Accpted by OJ.


  • 84
    R

    The solution contains two steps 1 Use BFS to construct a graph. 2. Use DFS to construct the paths from end to start.Both solutions got AC within 1s.

    The first step BFS is quite important. I summarized three tricks

    1. Using a MAP to store the min ladder of each word, or use a SET to store the words visited in current ladder, when the current ladder was completed, delete the visited words from unvisited. That's why I have two similar solutions.
    1. Use Character iteration to find all possible paths. Do not compare one word to all the other words and check if they only differ by one character.
    1. One word is allowed to be inserted into the queue only ONCE. See my comments.
    public class Solution {
    	Map<String,List<String>> map;
    	List<List<String>> results;
        public List<List<String>> findLadders(String start, String end, Set<String> dict) {   	
            results= new ArrayList<List<String>>();
            if (dict.size() == 0)
    			return results;
            
            int min=Integer.MAX_VALUE;
            
            Queue<String> queue= new ArrayDeque<String>();
            queue.add(start);
            
    		map = new HashMap<String,List<String>>();
    		
    		Map<String,Integer> ladder = new HashMap<String,Integer>();
    		for (String string:dict)
    		    ladder.put(string, Integer.MAX_VALUE);
    		ladder.put(start, 0);
    				
    		dict.add(end);
    		//BFS: Dijisktra search
    		while (!queue.isEmpty()) {
    		   
    			String word = queue.poll();
    			
    			int step = ladder.get(word)+1;//'step' indicates how many steps are needed to travel to one word. 
    			
    			if (step>min) break;
    			
    			for (int i = 0; i < word.length(); i++){
    			   StringBuilder builder = new StringBuilder(word); 
    				for (char ch='a';  ch <= 'z'; ch++){
    					builder.setCharAt(i,ch);
    					String new_word=builder.toString();				
    					if (ladder.containsKey(new_word)) {
    							
    					    if (step>ladder.get(new_word))//Check if it is the shortest path to one word.
    					    	continue;
    					    else if (step<ladder.get(new_word)){
    					    	queue.add(new_word);
    					    	ladder.put(new_word, step);
    					    }else;// It is a KEY line. If one word already appeared in one ladder,
    					          // Do not insert the same word inside the queue twice. Otherwise it gets TLE.
    					    
    					    if (map.containsKey(new_word)) //Build adjacent Graph
    					    	map.get(new_word).add(word);
    					    else{
    					    	List<String> list= new LinkedList<String>();
    					    	list.add(word);
    					    	map.put(new_word,list);
    					    	//It is possible to write three lines in one:
    					    	//map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
    					    	//Which one is better?
    					    }
    					    
    					    if (new_word.equals(end))
    					    	min=step;
    
    					}//End if dict contains new_word
    				}//End:Iteration from 'a' to 'z'
    			}//End:Iteration from the first to the last
    		}//End While
    
        	//BackTracking
    		LinkedList<String> result = new LinkedList<String>();
    		backTrace(end,start,result);
    
    		return results;        
        }
        private void backTrace(String word,String start,List<String> list){
        	if (word.equals(start)){
        		list.add(0,start);
        		results.add(new ArrayList<String>(list));
        		list.remove(0);
        		return;
        	}
        	list.add(0,word);
        	if (map.get(word)!=null)
        		for (String s:map.get(word))
        			backTrace(s,start,list);
        	list.remove(0);
        }
    }
    

    Another solution using two sets. This is similar to the answer in the most viewed thread. While I found my solution more readable and efficient.

    public class Solution {
    	List<List<String>> results;
    	List<String> list;
    	Map<String,List<String>> map;
    	    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    	        results= new ArrayList<List<String>>();
    	        if (dict.size() == 0)
    				return results;
    	        
    	        int curr=1,next=0;	        
    	        boolean found=false;	        
    	        list = new LinkedList<String>();	       
    			map = new HashMap<String,List<String>>();
    			
    			Queue<String> queue= new ArrayDeque<String>();
    			Set<String> unvisited = new HashSet<String>(dict);
    			Set<String> visited = new HashSet<String>();
    			
    			queue.add(start);			
    			unvisited.add(end);
    			unvisited.remove(start);
    			//BFS
    			while (!queue.isEmpty()) {
    			   
    				String word = queue.poll();
    				curr--;				
    				for (int i = 0; i < word.length(); i++){
    				   StringBuilder builder = new StringBuilder(word); 
    					for (char ch='a';  ch <= 'z'; ch++){
    						builder.setCharAt(i,ch);
    						String new_word=builder.toString();	
    						if (unvisited.contains(new_word)){
    							//Handle queue
    							if (visited.add(new_word)){//Key statement,Avoid Duplicate queue insertion
    								next++;
    								queue.add(new_word);
    							}
    							
    							if (map.containsKey(new_word))//Build Adjacent Graph
    								map.get(new_word).add(word);
    							else{
    								List<String> l= new LinkedList<String>();
    								l.add(word);
    								map.put(new_word, l);
    							}
    							
    							if (new_word.equals(end)&&!found) found=true;		
    														
    						}
    
    					}//End:Iteration from 'a' to 'z'
    				}//End:Iteration from the first to the last
    				if (curr==0){
    					if (found) break;
    					curr=next;
    					next=0;
    					unvisited.removeAll(visited);
    					visited.clear();
    				}
    			}//End While
    
    			backTrace(end,start);
    			
    			return results;        
    	    }
    	    private void backTrace(String word,String start){
    	    	if (word.equals(start)){
    	    		list.add(0,start);
    	    		results.add(new ArrayList<String>(list));
    	    		list.remove(0);
    	    		return;
    	    	}
    	    	list.add(0,word);
    	    	if (map.get(word)!=null)
    	    		for (String s:map.get(word))
    	    			backTrace(s,start);
    	    	list.remove(0);
    	    }
    	}

  • 2
    A

    For your first solution, in the backTrace function, how do you make sure the paths being put in result are shortest paths?


  • 4
    R

    It is a Directed Graph, all the path starts from the'end' and ends at'start'. All of them are the shortest, otherwise it wll not be added to the graph.


  • 0
    A

    I see. Thanks!


  • 0
    S

    Hi. What if dict.size() == 0 and start == end?


  • 0
    R

    if dict.size()== 0 return an empty list.


  • 10
    A

    Hi, nice solution, but seems that line

    dict.add(end);
    

    should be before the for loop, otherwise the graph doesn't contain end at all.
    It will pass OJ through, probably because in all test cases dict already contains end.


  • 0
    R

    I agree with you.


  • 1
    N

    Hi, thank you for sharing, but I have a little double about your first solution.
    In your first solution, you use a map : String -> List of Strings to store the shortest path from start to the current word. But what if there are multiple shortest paths out there?
    Because you use the map to backtrack the final results, I'm afraid you may miss some of the paths due to the reason that you only record one of the shortest paths for every word?


  • 0
    M
    This post is deleted!

  • 0
    Q

    clear idea. BFS then DFS.


  • 0
    O

    Can't agree with you more! It seems like that the OJ doesn't include sample test case.


  • 0

    Here is my 88ms c++ solution use two-end BFS :

    class Solution {
    public:
        std::vector<std::vector<std::string> > findLadders(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
            std::vector<std::vector<std::string> > paths;
            std::vector<std::string> path(1, beginWord);
            if (beginWord == endWord) {
                paths.push_back(path);
                return paths;
            }
            std::unordered_set<std::string> words1, words2;
            words1.insert(beginWord);
            words2.insert(endWord);
            std::unordered_map<std::string, std::vector<std::string> > nexts;
            bool words1IsBegin = false;
            if (findLaddersHelper(words1, words2, dict, nexts, words1IsBegin))
                getPath(beginWord, endWord, nexts, path, paths);
            return paths;
        }
    private:
        bool findLaddersHelper(
            std::unordered_set<std::string> &words1,
            std::unordered_set<std::string> &words2,
            std::unordered_set<std::string> &dict,
            std::unordered_map<std::string, std::vector<std::string> > &nexts,
            bool &words1IsBegin) {
            words1IsBegin = !words1IsBegin;
            if (words1.empty())
                return false;
            if (words1.size() > words2.size())
                return findLaddersHelper(words2, words1, dict, nexts, words1IsBegin);
            for (auto it = words1.begin(); it != words1.end(); ++it)
                dict.erase(*it);
            for (auto it = words2.begin(); it != words2.end(); ++it)
                dict.erase(*it);
            std::unordered_set<std::string> words3;
            bool reach = false;
            for (auto it = words1.begin(); it != words1.end(); ++it) {
                std::string word = *it;
                for (auto ch = word.begin(); ch != word.end(); ++ch) {
                    char tmp = *ch;
                    for (*ch = 'a'; *ch <= 'z'; ++(*ch))
                        if (*ch != tmp)
                            if (words2.find(word) != words2.end()) {
                                reach = true;
                                words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                            }
                            else if (!reach && dict.find(word) != dict.end()) {
                                words3.insert(word);
                                words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                            }
                    *ch = tmp;
                }
            }
            return reach ? true : findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
        }
    private:
        void getPath(
            std::string beginWord,
            std::string &endWord,
            std::unordered_map<std::string, std::vector<std::string> > &nexts,
            std::vector<std::string> &path,
            std::vector<std::vector<std::string> > &paths) {
            if (beginWord == endWord)
                paths.push_back(path);
            else
                for (auto it = nexts[beginWord].begin(); it != nexts[beginWord].end(); ++it) {
                    path.push_back(*it);
                    getPath(*it, endWord, nexts, path, paths);
                    path.pop_back();
                }
        }
    };

  • 0
    D

    Nice answer. But for your first solution can you explain me how the ‘end’ is added to map as a key for latter backtrace? Since the ladder in initialized before the end is added to the dict, In the nested for loops, you check if the new_word is in ladder and then add it to the map as key. There should be no way for the end to be added because it is not even in the ladder.

    I know it work but I just couldn’t figure it out.


  • 0
    S

    Hi, it seems to me that the map does not really store the shortest path from start to the current word. Instead, as suggested by the code comment, the map stores an adjacency list (to represent a directed graph). Then the directed graph is used to construct the shortest paths.


  • 1
    Z

    Maybe in solution 1 "dict.add(end)" should go before for (String string:dict) ... ladder.put(string, Integer.MAX_VALUE). Ladder should contain end, isn't it?
    In solution 2, Using visited instead of queue can avoid duplicate queue insertion well, just in the end of while q loop add q = visited.


  • 1

    Please correct it. I am really confused for a long time.


  • 0
    L

    me too ,very confused about that!


  • 0
    M

    Hi reeclappe. I myself got confused when I debugged the code. Ladder map should contain the end word because that when it is being checked inside if (ladder.containsKey(new_word))
    {
    if (new_word.equals(end))
    min=step;
    }


  • 0
    W

    Hi, in the bfs part of 1st solution,

    if (step<ladder.get(new_word))
    why do you need to check the new word ladder may be larger than a step? In my understanding, BFS touches node level by level(from close to far), so there should be no possibility that a re-visited word's distance is shorter than the distance it was previously visited. Please correct me if I have any mistake here. Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.