127.单词接龙（双向DFS）

Array.prototype.isEmpty = function () {
    return this.length === 0 ? true : false;
}
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
    let set = new Set();
    // 将wordList保存在集合中
    for (const w of wordList) {
        set.add(w);
    }
    if (!set.has(endWord))
        return 0;
    let ans = bfs();
    return ans === -1 ? 0 : ans + 1;
    function bfs() {
        // d1代表从起点beginWord开始搜索（正向）
        // d2代表从结尾endWord开始搜索（反向）
        let d1 = new Array();
        let d2 = new Array();
        /**
         * m1和m2分别记录两个方向出现的单词是经过多少次转换而来
         * eg:
         * m1 = {"abc":1} 代表 abc 由 beginWord 替换 1 次字符而来
         * m2 = {"xyz":3} 代表 xyz 由 endWord 替换 3 次字符而来
         */
        let m1 = new Map();
        let m2 = new Map();
        d1.push(beginWord);
        m1.set(beginWord, 0);
        d2.push(endWord);
        m2.set(endWord, 0);
        /*
         * 只有两个队列都不空，才有必要继续往下搜索
         * 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
         * eg:
         * 例如，如果 d1 为空了，说明从 beginWord 搜索到底都搜索不到 endWord，反向搜索也没必要进行了
         */
        while (!d1.isEmpty() && !d2.isEmpty()) {
            let t = -1;
            // 为了平衡两个方向搜索的程度，通过队列长度来确定执行哪个
            if (d1.length <= d2.length) {
                // 更新队列d1
                t = update(d1, m1, m2);
            } else {
                // 更新队列d2
                t = update(d2, m2, m1);
            }
            if (t != -1) {
                return t;
            }
        }
        return -1;
    }
    /**
     * 从queue中取出一个单词进行扩展，
     * @param {Array} queue 当前方向队列
     * @param {Map} cur 当前方向的距离字典
     * @param {*} other 另外一个方向的距离字典
     * @returns 转换次数
     */
    function update(queue, cur, other) {
        // 获取当前需要扩展的字符串
        const curWord = queue.shift();
        let n = curWord.length;
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < 26; j++) {
                // 将字符串第i个元素更新，更新范围是a~z，是26个
                const newChar = String.fromCharCode('a'.charCodeAt() + j);
                const nextWord = curWord.substring(0, i) + newChar + curWord.substring(i + 1);
                if (set.has(nextWord)) {
                    // 如果该字符在当前方向扩展过，就跳过
                    if (cur.has(nextWord))
                        continue;
                    // 如果在另一个方向出现过，说明找到了连通两个方向的最短路径
                    if (other.has(nextWord)) {
                        return cur.get(curWord) + 1 + other.get(nextWord);
                    } else {
                        // 没有出现的话就加入到这个方向的队列中
                        queue.push(nextWord);
                        cur.set(nextWord, cur.get(curWord) + 1);
                    }
                }
            }
        }
        return -1;
    }
};