My Java updated two-end BFS with some speed up tricks and comments


  • 2
    M

    Because list.contains() is not constant, Directly using list.contains() will get TLE.
    So the key change is to transfer list to hashset in order to remain constant check time. Below are some speed up tricks and comments. Hope this will help.

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if(!wordList.contains(endWord)) return 0;
            Set<String> startSet=new HashSet<String>(),endSet=new HashSet<String>(),list=new HashSet<String>();
            startSet.add(beginWord);
            endSet.add(endWord);
            int len=1;
            for(String temp:wordList){
                list.add(temp);//transfer list to hashset
            }
            while(!startSet.isEmpty()&&!endSet.isEmpty()){
                if(startSet.size()>endSet.size()){
                    Set tmpSet=startSet;//search with less word's set to speed up
                    startSet=endSet;
                    endSet=tmpSet;
                }
                    
                Set<String> tmp=new HashSet<String>();
                for(String word:startSet){
                    char[] charArr=word.toCharArray();// put this out of the inner for loop to initialize less times. This would require to remember the changed character
                    for(int i=0;i<word.length();i++){
                        for(char c='a';c<='z';c++){
                            char replace=charArr[i];//remember the changed character and change it back later
                            charArr[i]=c;
                            String s=new String(charArr);
                            if(endSet.contains(s)) return len+1;
                            //if other set contains string s means there is a intersect point between two sets. So return
                            if(list.contains(s)){//HashSet contains is constant while List is not.
                                tmp.add(s);
                                list.remove(s);
                            }
                            charArr[i]=replace;//change it back
                        }
                    }
                }
                startSet=tmp;
                
                len++;
            }
            return 0;
        }
    

Log in to reply
 

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