LeetCode - 127. Word Ladder (python)

https://leetcode.com/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150

• 난이도 : hard
• 알고리즘 : BFS

접근방법

• 현재 단어에서 한 글자만이 바뀐 단어로 이동, 이 때 이미 거쳐간 단어는 다시 탐색할 필요가 없다
• set 자료형을 사용하여 O(1) 시간에 탐색을 수행한다
• 현재 단어에서 한 문자만을 바꾼 새로운 단어를 만들고 해당 단어가 wordSet에 있다면 큐에 depth와 함께 넣고 해당 단어를 wordSet에서 삭제한다
• 큐에서 꺼낸 word가 endWord와 같다면 탈출하여 해당 depth를 리턴한다

소스코드

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordLength = len(wordList[0])
        curWordSet = set(wordList)
        dq = collections.deque()
        answer = 0

        if endWord not in curWordSet:
            return 0

        dq.append((beginWord, 1))
        while dq:
            word, depth = dq.popleft()

            if word == endWord:
                answer = depth
                break

            for i in range(wordLength):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    newWord = word[:i] + c + word[i+1:]

                    if newWord in curWordSet:
                        curWordSet.discard(newWord)
                        dq.append((newWord, depth + 1))

        return answer