Share my AC BFS only, without backtracking solution


  • 0
    L

    The idea is to maintain the result list for each level of BFS.

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            HashMap<String, List<List<String>>> map = new HashMap<>();
            HashSet<String> queue = new HashSet<> ();
            HashSet<String> dict = new HashSet<>(wordList);
            int length = beginWord.length();
            
            queue.add(beginWord);
            List<List<String>> beginList = new LinkedList<> ();
            LinkedList<String> a = new LinkedList<String>();
            a.add(beginWord);
            beginList.add(a);
            map.put(beginWord, beginList);
            while(!queue.isEmpty()) {
                HashSet<String> newQueue = new HashSet<>();
                HashMap<String, List<List<String>>> newMap = new HashMap<>();
                if(queue.contains(endWord)) break;
                for(String s : queue) {
                    List<List<String>> currList = map.get(s);
                    if(currList == null)    continue;   
                    dict.remove(s);
                    //map.remove(s);
                    char[] cs = s.toCharArray();
                    for(int i = 0; i < length; i ++) {
                        char curr = cs[i];
                        for(int j = 0; j < 26; j ++) {
                            cs[i] = (char)(j + 'a');
                            if(curr == cs[i])   continue;
                            String replaced = new String(cs);
                            if(dict.contains(replaced)) {
                                List<List<String>> nextList = newMap.getOrDefault(replaced, new LinkedList<>());
                                for(List<String> list : currList) {
                                    List<String> temp = new ArrayList<>(list);
                                    temp.add(replaced);
                                    nextList.add(temp);
                                }
                                newQueue.add(replaced);
                                newMap.put(replaced, nextList);
                            }
                        }
                        cs[i]=curr;
                    }
                    
                    
                    
                }
                
                queue = newQueue;
                map = newMap;
                
            }
            
            return map.getOrDefault(endWord, new LinkedList<>());
        }
    

Log in to reply
 

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