BFS solution causing Time Limit


  • 0
    P
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            HashSet<String> reached = new HashSet<String>();
            reached.add(beginWord);
            HashSet<String> unreached = new HashSet<String>();
            unreached.addAll(wordList);
            unreached.add(endWord);
            if(beginWord.equals(endWord)) return 2; 
            int distance = 2; 
            while(!unreached.isEmpty()){
                HashSet<String> toAdd = new HashSet<String>();
                for(String word: unreached) {
                    for(String reachedWord : reached) {
                        if(transformable(reachedWord, word)) {
                            toAdd.add(word);
                            break;
                        }
                            
                    }
                }
                if(toAdd.isEmpty()) return 0;
                if(toAdd.contains(endWord)) return distance; 
                distance++;
    
                reached.addAll(toAdd);
                for(String s : toAdd) {
                    unreached.remove(s);
                }
            }
            return 0; 
            
        }
        
        public boolean transformable(String a, String b) {
            int distance = 0;
            for(int i=0; i<a.length(); i++) {
                distance += (a.charAt(i) != b.charAt(i))? 1: 0;
                if(distance>1) return false;
                
            }
            return true; 
        }
        
        
            
        
    } 
    

    Here is my BFS solution. I think the logic is similar to other people's accepted code, except that I used a slightly different method to see if two words are transformable.

    I noticed that others tries changing one character of the given word and see if the modified word exists in the word list. Is my "transformable" function particularly inefficient? Or is there something inefficient about my BFS method?

    Can you please guide? Thanks.


  • 1
    L

    I just met the same question as you.
    In my opinion, for example, you have a list with 100 words, length of each word is 5.
    Then with your solution, we need to compare 5*100=500 times for the first time,
    and using others solution, it needs only 5*26=130 comparison.

    So it's much faster.


Log in to reply
 

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