단어 사다리

사전beginWord을 사용하여 단어endWord에서 단어wordList로의 변환 시퀀스는 다음과 같은 단어 시퀀스beginWord -> s1 -> s2 -> ... -> sk입니다.

인접한 모든 단어 쌍은 단일 문자로 다릅니다.

si에 대한 모든 1 <= i <= k는 wordList에 있습니다. beginWord가 wordList에 있을 필요는 없습니다.

sk == endWord

두 단어 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"가 wordList에 없으므로 유효한 변환 순서가 없습니다.

제약:

1 <= beginWord.length <= 10

endWord.length == beginWord.length

1 <= wordList.length <= 5000

wordList[i].length == beginWord.length

beginWord , endWord 및 wordList[i] 는 영문 소문자로 구성됩니다.

beginWord != endWord

wordList의 모든 단어는 고유합니다.

해결책:

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        n = len(beginWord)
        wordList = set(wordList + [beginWord])
        graph = {}
        for word in wordList:
            for i in range(n):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    currstr = word[0:i] + c + word[i+1:]
                    if currstr != word and currstr in wordList:
                        if word in graph:
                            graph[word].append(currstr)
                        else:
                            graph[word] = [currstr]
        dist = {}
        dist[beginWord] = 1
        queue = [(beginWord, 1)]
        visited = set()
        i = 0
        while i < len(queue):
            curr, k = queue[i]
            for j in graph.get(curr, []):
                if j not in visited:
                    dist[j] = dist.get(curr, float('inf')) + 1
                    if j == endWord:
                        return k + 1
                    visited.add(j)
                    queue.append((j, k + 1))
            i += 1
        return 0