WordDistanceTwoEndsBFS.java

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return 0; 
        Set<String> s1 = new HashSet<>(); 
        Set<String> s2 = new HashSet<>();
        Set<String> visited = new HashSet<>(); 
        s1.add(beginWord);
        s2.add(endWord);
        int result = 1; 
        
        while (s1.size() != 0 && s2.size() != 0) {
            if (s2.size() > s1.size()) {
                Set<String> temp = s1; 
                s1 = s2; 
                s2 = temp; 
            }
            
            Set<String> temp = new HashSet<>(); 
            for (String word : s1) {
                char[] arr = word.toCharArray(); 
                for (int i = 0; i < arr.length; i++) {
                    char oldChar = arr[i]; 
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c; 
                        String next = String.valueOf(arr);
                        if (s2.contains(next)) return result + 1; 
                        if (!visited.contains(next) && dict.contains(next)) {
                            visited.add(next);
                            temp.add(next);
                        }
                    }
                    arr[i] = oldChar; 
                } 
            }
            s1 = temp; 
            result++;
        }
        
        return 0; 
    }
}