leetcode题解127：单词接龙

描述

分析

有了第126题的解法后，该题就简单多了，由于不需要记录具体路径，从而只需要记录最后一个节点即可。例子如下：

初始为paths = [beginWord]
取beginWord的所有相邻节点，添加到路径，假设结果为paths=[node1, node2]
记录访问过的节点node1, node2，
在遍历下一层之间，注意从所有节点中去掉访问过的节点，
从上一次的结果paths遍历，得到新的相邻节点，假设新结果为[node3, node4]
一直迭代下去，直到遇到结束节点退出。

这里的paths只记录的当前层的节点，所以当遍历完上一层的paths时，层数更新即可。

代码

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        alphabeta = [chr(i) for i in range(ord('a'), ord('a')+26)]
        word_list = set(wordList)
        level_arr = [beginWord]     # 当前层节点
        visited = set([beginWord])  # 访问过的结点
        res = 0
        while len(level_arr) > 0:
            res += 1
            level_len = len(level_arr)
            while level_len > 0:
                s = level_arr.pop(0)
                for i in range(len(s)):
                    for c in alphabeta:
                        new_s = s[:i] + c + s[i+1:]
                        if new_s in word_list and new_s == endWord:
                            return res + 1
                        if new_s not in word_list or new_s in visited:
                            continue
                        level_arr.append(new_s)
                        visited.add(new_s)
                level_len -= 1
        return 0