[leetcode 매일 풀기] 126. word ladder 3

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

Word Ladder II - LeetCode

 

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

 

최단경로를 요구하기 때문에 bfs로 탐색을 진행해야겠다고 생각하고, 대충 queue에 상태를 넣어서 구현하면 되겠지 라는 생각을 하면서 구현을 했다.

 

class Solution:
    def findLadders(
        self, beginWord: str, endWord: str, wordList: List[str]
    ) -> List[List[str]]:
        queue: List[(str, Set[str], List[str])] = []

        def word_distance(s1: str, s2: str) -> int:
            count = 0
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    count += 1
            return count

        results = []
        shortest_length = math.inf
        queue.append((beginWord, set(wordList), [beginWord]))
        while queue:
            curr_state, remain_words, path = queue.pop(0)

            if len(path) > shortest_length:
                continue

            if curr_state == endWord:
                results.append(path)
                shortest_length = min(len(path), shortest_length)

            for remain_word in remain_words:
                if word_distance(curr_state, remain_word) == 1:
                    next_remain_words = remain_words.copy()
                    next_remain_words.remove(remain_word)

                    next_state = (remain_word, next_remain_words, path + [remain_word])
                    queue.append(next_state)
        return results

 

 

흔히 보는 TimeLimitExceeded가 뜨는게 아닌, MemoryLimitExceeded가 떠서 memory를 줄일방법을 고민해야 했다.

 

일단 다음 상태를 관리하는 입장에서 다음 word를 저장하는 것 뿐만이 아니라, 탐색가능한 word들을 저장하고 있는 부분을 줄여야 한다고 생각이 들었지만, 아이디어가 떠오르지 않았었는데.

다른 사람들의 코드를 보니, 최단거리로 탐색하는 것이기 때문에 돌아서 오게 되는 경우는 굳이 탐색을 하지 않아도 되는 부분이었고. 최단거리로 특정 단어에 도착할 경우, 다음 길이의 경로에서는 해당 단어를 탐색할 필요가 없어서 한개만 유지해도 된다는 것을 알 수 있었다.

 

Memory 사용량 관점은 아니고,  time complexity 관점에서 bfs의 다음 경로를 탐색하는 방법도 달랐는데.

나는 가능한 다음 set에 있는 word와, 현재의 word의 차이가 1이 나는 경우에 추가하는 방식으로 구현을 했는데.

다른 사람들은 현재의 word에서 1 차이가 나는 word를 만들어 가능한 다음 set에 추가하는 방식으로 구현을 했다.

 

이건 실제 input data가 어떻게 들어오느냐에 따라서 많이 갈릴 수 있을 것 같은데. 둘다 구현해봤을 때, leetcode의 case에서는 다른사람들의 방식이 두배정도 빠른것을 확인할 수 있었다.

 

최종 코드는 아래와 같다.

 

from collections import defaultdict
from typing import List


class Solution:
    def findLadders(
        self, beginWord: str, endWord: str, wordList: List[str]
    ) -> List[List[str]]:
        wordSet = set(wordList)
        layer = {beginWord}
        parent = defaultdict(set)
        time_to_break = False
        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
                            parent[new_word].add(word)
                            new_layer.add(new_word)

            if time_to_break:
                break
            wordSet -= new_layer
            layer = new_layer

        result = []

        def build_path(last, lst):
            if last == beginWord:
                result.append(list(reversed(lst)))
                return
            for word in parent[last]:
                build_path(word, lst + [word])

        build_path(endWord, [endWord])
        return result


assert Solution().findLadders(
    "hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]
) == [["hit", "hot", "lot", "log", "cog"], ["hit", "hot", "dot", "dog", "cog"]]
assert Solution().findLadders("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == []
assert Solution().findLadders("a", "c", ["a", "b", "c"]) == [["a", "c"]]
assert Solution().findLadders("hot", "dog", ["hot", "dog"]) == []
assert Solution().findLadders("hot", "dog", ["hot", "dog", "dot"]) == [
    ["hot", "dot", "dog"]
]
assert Solution().findLadders(
    "hot", "dog", ["hot", "cog", "dog", "tot", "hog", "hop", "pot", "dot"]
) == [["hot", "dot", "dog"], ["hot", "hog", "dog"]]

 

제출결과는 이렇게 나왔다.

 

 

히스토그램을 봤을 때, 앞에 다른 종류의 알고리즘을 사용한 것인가 해서 살펴봤는데.

 

bfs에서 다음 state를 찾을 때 더 빠르게 하기 위해서 adjacency matrix를 구현하는 방법으로 되어 있었다.

어떻게 만들 수 있을 까 감이 안와서 시도해지 못했었는데, 

 

d = defaultdict(list)
for word in wordList:
    for i in range(len(word)):
        d[word[:i]+"*"+word[i+1:]].append(word)

 

이렇게 만들게 되면, 조금 더 빠르게 다음 word를 찾을 수 있는 것을 볼 수 있었다.

이부분까지는 따라하지 않았지만, 다른 사람 코드를 보면서 배우는게 많은 문제였다.