Bi-BFS

双向BFS算法，适用于起点和终点都给定的情况，求最短路径，即两个Set首次相交的情况

经典题目：Word ladder

• 用两个set, beginSet and endSet

• 不需要Queue

• 每次确保 beginSet.size() < endSet.size()

• 然后iterate element in beginSet to find neighbors

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //beginSet, endSet, tmpSet, visitedSet
        //fetch smaller set from beginSet and endSet, then check each of word in the set to see whether it's in wordList
        //if not, then add all unvisited neighbors to set
        Set<String> beginSet = new HashSet<>();
        beginSet.add(beginWord);
        Set<String> endSet = new HashSet<>();
        endSet.add(endWord);

        Set<String> visited = new HashSet<>();
        int len = 1;

        Set<String> wordSet = convertToSet(wordList);

        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (endSet.size() < beginSet.size()) {
                swap(beginSet, endSet);
            }
            Set<String> tmp = new HashSet<>();
            for (String cur : beginSet) {
                //get list of next words of cur from wordList
                List<String> nextWords = getNextWords(cur, wordSet, visited);
                for (String nextWord : nextWords) {
                    if (nextWord.equals(endWord)) {
                        return len + 1;
                    }
                    visited.add(nextWord);
                    tmp.add(nextWord);
                }
            }
            beginSet = tmp;
            len++;
        }
        return 0;
    }

    private Set<String> convertToSet(List<String> wordList) {
        Set<String> wordSet = new HashSet<>();
        for (String word : wordList) {
            wordSet.add(word);
        }
        return wordSet;
    }

    private void swap(Set<String> beginSet, Set<String> endSet) {
        Set<String> tmp = beginSet;
        beginSet = endSet;
        endSet = tmp;
    }

    private List<String> getNextWords(String curWord, Set<String> dict, Set<String> visited) {
        List<String> res = new ArrayList<>();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < curWord.length(); i++) {
                if (curWord.charAt(i) == c) {
                    continue;
                }
                String newWord = replace(curWord, i, c);
                if (!visited.contains(newWord) && dict.contains(newWord)) {
                    res.add(newWord);
                }
            }
        }
        return res;
    }

    private String replace(String word, int index, char c) {
        char[] charArr = word.toCharArray();
        charArr[index] = c;
        return new String(charArr);
    }
}