leetCode--单词接龙--BFS_leetcode bfs单词

单词接龙

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

1.每次转换只能改变一个字母。
2.转换过程中的中间单词必须是字典中的单词。
1
2

说明:

1.如果不存在这样的转换序列，返回 0。
2.所有单词具有相同的长度。
3.所有单词只由小写字母组成。
4.字典中不存在重复的单词。
5.你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
1
2
3
4
5

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",返回它的长度 5。
1
2
3
4
5
6

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。
1
2
3
4
5
6

思路：bfs进行层序遍历，每一层获取到一个符合条件的值就将该值从wordList中删除，到达尾结点直接返回长度。

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */

var ladderLength = function (beginWord, endWord, wordList) {
    /* 判断是否相差字母数小于1 */
    function judge(s1, s2) {
        let cnt = 0;/* 相差个数 */
        for (let i = 0; i < s1.length; i++) {
            if (s1[i] !== s2[i]) cnt++;
            if (cnt > 1) return false;
        }
        return true;
    }
    // 队列记录当前层的序列
    let queue = [beginWord];
    let level = 1;//层数
    while (queue.length) {
        let size = queue.length;/* 当前层的个数 */
        while (size--) {
            let front = queue.shift();/* 弹出并取出队头 */
            /* 遍历查找相似的串 */
            for (let i = 0; i < wordList.length; i++) {
                let next = wordList[i];
                /* 判断条件 */
                if (judge(front, next)) {
                    /* 结尾直接返回长度，否则放到下一层 */
                    if (next === endWord) {
                        return level + 1;
                    } else {
                        queue.push(next);
                        /* 删除结点，提升性能 */
                        wordList.splice(i, 1);
                        i--;
                    }
                }
            }
        }
        level++;
    }
    return 0;
};

let res = ladderLength(
    "hit",
    "cog",
    ["hot", "dot", "dog", "lot", "log", "cog"]
)
console.log(res);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52