Why BFS TLE? It's that the recalculation of some path?


  • 0
    B
      public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
                //bfs
         List<List<String>>  ans = new ArrayList<>();
        if(beginWord.length()!= endWord.length()) return ans;
        int len = endWord.length();
        wordList.add(endWord);//!important
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        Queue<List<String>> listQ = new LinkedList<>();
        List<String> startList = new ArrayList<>();
        startList.add(beginWord);
        listQ.add(startList);
        q.add(beginWord);
        // boolean found = false;//1.important 2.not working
        while(!q.isEmpty()){
            int size = q.size();
            Set<String> level = new HashSet<>();
            for(int k = 0; k < size; k++){
                String str = q.poll();
                List<String> list = listQ.poll();
                if((!visited.add(str)&&!str.equals(endWord)&&!level.contains(str))||(ans.size()>0&&ans.get(0).size()<list.size())) continue;
                if(str.equals(endWord)){ans.add(list);continue;}
                for(int i = 0; i < 26; i++){
                    for(int j = 0; j < len;j++){
                        char[] array = str.toCharArray();
                        char c = (char) (i+'a');
                        if(c!=str.charAt(j)){
                            array[j] = c;
                            String s = new String(array);
                            if(visited.contains(s)) continue;//!important
                            if(wordList.contains(s)){
                                q.add(s);
                                list.add(s);
                                listQ.add(new ArrayList<String>(list));
                                list.remove(list.size()-1);
                            } 
                        }
                        
                    }
                }
                level.add(str);
            }
            
        }
        return ans;
    }

Log in to reply
 

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