[127]word ladder

以下使用双向bfs解法。
利用two queue, two hashset.

同时采取check两个set的size的方式选择选取哪一边进行bfs。

import java.util.*;

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

        Set<String> leftSet = new HashSet<>();
        Set<String> rightSet = new HashSet<>();

        Queue<String> leftq = new LinkedList<>();
        Queue<String> rightq = new LinkedList<>();

        if(beginWord == endWord)return 1;

        leftSet.add(beginWord);
        rightSet.add(endWord);
        leftq.offer(beginWord);
        rightq.offer(endWord);

        int path = 1;

        while(!leftq.isEmpty() && !rightq.isEmpty()){
            Queue<String> q = leftq;
            Set<String> set = leftSet;
            Set<String> oset = rightSet;
            if(leftq.size() > rightq.size()){
                q = rightq;
                set = rightSet;
                oset = leftSet;
            }

            int size = q.size();
            path++;

            for(int k = 0; k < size; k++){
                String cur = q.poll();
                char[] arr = cur.toCharArray();
                for(int i = 0; i < cur.length(); i++){
                    char ori = arr[i];
                    for(char c = 'a'; c <= 'z'; c++){
                        arr[i] = c;
                        String ns = new String(arr);
                        if(set.contains(ns) || !wordList.contains(ns))continue;
                        else{
                            if(oset.contains(ns))return path;
                            q.offer(ns);
                            set.add(ns);
                        }
                    }
                    arr[i] = ori;
                }

            }
        }
        
        return 0;
    }

    public static void main(String[] args){
        Solution s = new Solution();


        Set<String> set = new HashSet<>(Arrays.asList(new String[]{"hot","cog","dog","tot","hog","hop","pot","dot"}));
        System.out.println(s.ladderLength("hot","dog",set));

    }
}