当前位置:   article > 正文

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

leetcode bfs单词

单词接龙

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

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

说明:

1.如果不存在这样的转换序列,返回 02.所有单词具有相同的长度。
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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/718552
推荐阅读
相关标签
  

闽ICP备14008679号