81. LeetCode.127. 单词接龙

• 标签： 广度遍历
• 难度： 中等

---

• 题目描述

• 解法

以 beginWord 为根节点，逐层的构建树，每个子结点是父节点变化一个字符后，并且仍然在 wordlist 中的单词。 注意 wordlist 中用过的单词需要删除, 避免重复构建子结点.（为什么要避免？ 反证法参考）. 在逐层构造的过程中，若某个子结点是 endWord, 则返回其位置深度.

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        wordList.append(beginWord)
        fathers= [beginWord]
        children = []
        depth = 1
        n = len(beginWord)
        while fathers:
            for f in fathers:
                if f == endWord:
                    return depth
                for i in range(n):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        child = f[:i] + c + f[i+1:]
                        if child in wordList:
                            wordList.remove(child)
                            children.append(child)
            depth += 1
            fathers = children
            children = []
            
        return 0
                    

• 其他解法

暂略。