Java bidirectional BFS beats 93.18%


  • 0
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    
                Set<String> s1 = new HashSet<>();
                s1.add(beginWord);
                
                Set<String> s2 = new HashSet<>();
                s2.add(endWord);
                
                wordList.remove(beginWord);
                wordList.remove(endWord);
                
                return getLadderLength(s1,s2,wordList, 1);
        }
        
        private int getLadderLength(Set<String> s1, Set<String> s2, Set<String> dict, int len){
            if (s1.isEmpty() || s2.isEmpty()){
                return 0;
            }
            
            Set<String> neighb = new HashSet<>();
            
            for (String w : s1){
                char[] chars = w.toCharArray();
                for (int i = 0; i < chars.length; ++i){
                    char symb = chars[i];
                    for (char c = 'a'; c <= 'z'; ++c){
                        chars[i] = c;
                        String tmpWord = String.valueOf(chars);
                        if (s2.contains(tmpWord)){
                            return ++len;
                        } else if (dict.remove(tmpWord)){
                            neighb.add(tmpWord);
                        }
                    }
                    chars[i] = symb;
                }
            }
        
        
        if (neighb.size() > s2.size()){
            return getLadderLength(s2, neighb, dict, ++len);
        } else {
            return getLadderLength(neighb, s2, dict, ++len);
        }
        
    }
    

Log in to reply
 

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