python实现leetcode之127. 单词接龙

解题思路

这题与上一题思路类似
先构造一张图，临接节点就是将某个字符改为*
然后广度优先遍历整张图，找到endWord返回

127. 单词接龙

代码

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        graph = {}
        for wd in [beginWord] + wordList:
            if wd not in graph: graph[wd] = set()
            for i in range(len(wd)):
                if i == 0: pattern_wd = '*' + wd[i+1:]
                elif i == len(wd)-1: pattern_wd = wd[:i] + '*'
                else: pattern_wd = wd[:i] + '*' + wd[i+1:]
                if pattern_wd not in graph: graph[pattern_wd] = set()
                
                graph[wd].add(pattern_wd)
                graph[pattern_wd].add(wd)

        visited = {}
        queue = [(beginWord, 0)]
        while queue:
            wd, depth = queue.pop(0)
            if wd == endWord: return depth//2 + 1
            visited[wd] = True
            for nb in graph[wd]:
                if nb not in visited:
                    queue.append((nb, depth+1))
        return 0