[leetcode 매일 풀기] 127.word ladder

오늘 리뷰할 문제는 word ladder 이다.  https://leetcode.com/problems/word-ladder/

Word Ladder - LeetCode

이 문제는 시작단어, 끝 단어, 그리고 단어들의 목록이 있을 때. 시작단어에서 한개의 문자를 바꾸면서 끝단어로 갈 수 있는 가장짧은 방법의 갯수를 출력하는 문제이다.

 

경로를 출력하는 word ladder 2를 리뷰(https://heoseogi.tistory.com/41)했기 때문에, 바뀐 코드만 공유하고 리뷰를 마칠 예정입니다.

 

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        layer = {beginWord}
        time_to_break = False
        length = 1
        while layer:
            new_layer = set()

            for word in layer:
                for i in range(len(beginWord)):
                    for c in "abcdefghijklmnopqrstuvwxyz":
                        new_word = word[:i] + c + word[i + 1 :]
                        if new_word in wordSet:
                            if new_word == endWord:
                                time_to_break = True
                            new_layer.add(new_word)
            length += 1
            if time_to_break:
                return length
            wordSet -= new_layer
            layer = new_layer

        return 0

 

결과는 아래와 같고, adjacency matrix를 적용하면 개선이 될 듯 하다.