LeetCode: 126. Word Ladder II

개인적으로 어려웠던 문제...

A. 내가 푼 방법

일단 내가 푼 방법은 아래와 같다.

1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결)

2) 다익스트라 알고리즘으로 최단 경로를 찾는다.

나름 머리 써서 푼건데, 속도도 느리고 메모리 효율도 떨어져서 실망스럽다.

 

import heapq

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        if endWord not in wordList:
            return []
        if beginWord not in wordList:
            wordList.append(beginWord)
        s_idx = wordList.index(beginWord)
        e_idx = wordList.index(endWord)
        graph = [[] * len(wordList) for _ in range(len(wordList))]
        for i in range(len(wordList)):
            for j in range(i+1, len(wordList)):
                if self.num_disparity(wordList[i], wordList[j]) == 1:
                    graph[i].append(j)
                    graph[j].append(i)
        
        ret = []
        distance = [1001] * len(wordList)
        pq = []
        heapq.heappush(pq, [1, s_idx, [wordList[s_idx]]])
        distance[s_idx] = 1
        while pq:
            dist_u, u, wordTrain = heapq.heappop(pq)
            if u == e_idx:
                if len(wordTrain) == distance[u]:
                    ret.append(wordTrain)
                    continue
                else:
                    break
            if distance[u] < dist_u:
                continue
            for v in graph[u]:
                if distance[v] >= 1 + dist_u:
                    distance[v] = 1 + dist_u
                    heapq.heappush(pq, [distance[v], v, wordTrain+[wordList[v]]])
        return ret
        
    def num_disparity(self, w1, w2):
        num_disparity = 0
        for i, char in enumerate(w1):
            if char != w2[i]:
                num_disparity += 1
        return num_disparity

 

B. 괴수의 답안

- neighbor word를 찾는 알고리즘이 다르다.

- set 자료형을 아주 맛깔나게 썼다.

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordSet = set(wordList)
        if endWord not in wordSet:
            return []
        wordSet.discard(beginWord)
        
        def neighbors(word):
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    candidate = word[:i] + c + word[i+1:]
                    if candidate in wordSet:
                        yield candidate
        
        # level[word]: word까지 도달하는 모든 path의 list
        # e.g. level[got] = [['hit', 'hot', 'got'], ['hit', 'git', 'got']]
        level = {}
        level[beginWord] = [[beginWord]]
        
        while level:
            newlevel = defaultdict(list)
            for word, paths in level.items():
                if word == endWord:
                    return paths
                for neighbor in neighbors(word):
                    for path in paths:
                        newlevel[neighbor].append(path+[neighbor])
            wordSet -= set(newlevel.keys())
            level = newlevel
        
        return []

 

C. 나의 알고리즘 개선

다익스트라를 살려보고 싶어서 B의 neighbor word 알고리즘을 반영하였다.

import heapq

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordSet = set(wordList)
        if endWord not in wordSet:
            return []
        if beginWord not in wordSet:
            wordList.append(beginWord)
            wordSet.add(beginWord)
        
        idx_dict = defaultdict(int)
        for idx, word in enumerate(wordList):
            idx_dict[word] = idx
        
        s_idx = idx_dict[beginWord]
        e_idx = idx_dict[endWord]
        
        graph = [[] * len(wordList) for _ in range(len(wordList))]
        
        for u in range(len(wordList)):
            word = wordList[u]
            wordSet -= set([word])
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    candidate = word[:i] + c + word[i+1:]
                    if candidate in wordSet:
                        v = idx_dict[candidate]
                        graph[u].append(v)
                        graph[v].append(u)
        
        ret = []
        distance = [1001] * len(wordList)
        pq = []
        heapq.heappush(pq, [1, s_idx, [wordList[s_idx]]])
        distance[s_idx] = 1
        while pq:
            dist_u, u, wordTrain = heapq.heappop(pq)
            if u == e_idx:
                if len(wordTrain) == distance[u]:
                    ret.append(wordTrain)
                    continue
                else:
                    break
            if distance[u] < dist_u:
                continue
            for v in graph[u]:
                if distance[v] >= 1 + dist_u:
                    distance[v] = 1 + dist_u
                    heapq.heappush(pq, [distance[v], v, wordTrain+[wordList[v]]])
        return ret

 

참고로 결론은 B다.

속도, 코드 간결성, 메모리 모든 측면에서 압승~!