JAVA AC, one way DFS, with a simple optimization


  • 0
    T

    The trick is use a map to remember one character variations of each word along the path;
    i.e. for the nanny cloud test case, result is:

    nanny,canny,candy,sandy,sands,sends,seeds,sleds,slews,clews,clefs,cleft,cleat,bleat,bloat,float,flout,clout,cloud,aloud,
    nanny,danny,dandy,sandy,sands,sends,seeds,sleds,slews,clews,clefs,cleft,cleat,bleat,bloat,float,flout,clout,cloud,aloud,

    many duplicate words appears on the same level of BFS. that's the redundant work of my code. so the map fixes it.

    and also clear the map, after each level of BFS, as duplicates will only appear in the same level.

    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            Set<String> used = new HashSet<>();
            Queue<String> que = new LinkedList<>();
            Queue<List<String>> path = new LinkedList<>();
            
            que.add(beginWord);
            List<String> first = new ArrayList<>();
            first.add(beginWord);
            path.add(first);
            used.add(beginWord);
            
            List<List<String>> res = new ArrayList<>();
            if(beginWord.equals(endWord)){
                return res;
            }
            int len = beginWord.length();
            Map<String, List<String>> map = new HashMap<>();
            
            while(!que.isEmpty()){
                
                List<String> next = new ArrayList<>();
                
                while(!que.isEmpty()){
                    String x = que.poll();
                    List<String> p = path.poll();
                    if(isOK(endWord, x)){
                        p.add(endWord);
                        res.add(p);
                        continue;
                    }
                    
                    if(map.containsKey(x)){
                        for(String newWord : map.get(x)){
                            if(!used.contains(newWord)){
                                	List<String> pp = new ArrayList<>(p);
                                    next.add(newWord);
                                    pp.add(newWord);
                                    path.add(pp);
                                }
                        }    
                    } else{  
                        map.put(x, new ArrayList<String>());
                        for(int i = 0;i<len;i++){
                        	char c = x.charAt(i);
                        	for(int j = 0;j<26;j++) {
                        		if(j != c-'a'){
                        			String newWord = x.substring(0, i) + (char)('a' + j) + x.substring(i+1);
                        			if(wordList.contains(newWord) && !used.contains(newWord) && isOK(newWord, x)){
                                    	List<String> pp = new ArrayList<>(p);
                                        next.add(newWord);
                                        map.get(x).add(newWord);
                                        pp.add(newWord);
                                        path.add(pp);
                                    }
                        		}
                        	}
                        }
                    }
                }
                if(!res.isEmpty())
                    return res;
                    
                que.addAll(next);
                used.addAll(next);
                map.clear();
                
            }
            return res;
        }
        
        private boolean isOK(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>1)
                        return false;
                }
            }
            return diff == 1;
        }
        
    }

Log in to reply
 

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