0127-单词接龙

本文主要是介绍0127-单词接龙，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

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

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

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder

参考：

• https://leetcode-cn.com/problems/word-ladder/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you-2/

python

# 0127.单词接龙

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: [str]) -> int:
        """
        无向图，BFS
        :param beginWord:
        :param endWord:
        :param wordList:
        :return:
        """
        from typing import List
        from collections import deque
        wordSet = set(wordList)
        if len(wordSet) == 0 or endWord not in wordSet:
            return 0
        if beginWord in wordSet:
            wordSet.remove(beginWord)
        queue = deque()
        queue.append(beginWord)
        visited = set(beginWord)
        wordLen = len(beginWord)
        step = 1
        while queue:
            curSize = len(queue)
            for i in range(curSize):
                word = queue.popleft()
                word_list = list(word)
                for j in range(wordLen):
                    originChar = word_list[j]
                    for k in range(26):
                        word_list[j] = chr(ord('a')+k)
                        next_word = "".join(word_list)
                        if next_word in wordSet:
                            if next_word == endWord:
                                return step + 1
                            if next_word not in visited:
                                queue.append(next_word)
                                visited.add(next_word)
                    word_list[j] = originChar
            step += 1

        return 0

golang

待完善

这篇关于0127-单词接龙的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！