Two-way BFS Java 26ms


  • 0
    G

    public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {

        int len = 1;
        
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();
        set1.add(beginWord);
        set2.add(endWord);
        
        while(!set1.isEmpty() && !set2.isEmpty()){
            
            if(set1.size() > set2.size()){
                Set<String> temp = set1;
                set1 = set2;
                set2 = temp;
            }
            
            for(String word: set1){
                wordDict.remove(word);
            }
            
            for(String word: set2){
                wordDict.remove(word);
            }
            
            Set<String> temp = new HashSet<>();
            for(String word: set1){
                for(int i=0; i<word.length(); i++){
                    char[] a = word.toCharArray();
                    for(char c='a'; c<='z' ; c++){
                        a[i] = c;
                        
                        String newString = new String(a);
                        if(set2.contains(newString)){
                            return len+1;
                        }
                        
                        if(wordDict.contains(newString)){
                            temp.add(newString);
                        }
                    }
                }
            }
            
            set1 = set2;
            set2 = temp;
            len++;
        }
        
        return 0;
    

    }
    }


Log in to reply
 

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