[LeetCode 127][Hard][Python] Word Ladder - 상세 풀이

 

Problem

https://leetcode.com/problems/word-ladder/

---

문제 접근

1-1. 문제 분석

본 문제는 주어진 단어 리스트에 대하여 '쌍' 관계 규칙을 통해 Startword → Endword 변환 과정에 대한 최단 경우에 대하여 묻는 문제이다. 

 

첫째, 단어간 한 글자 차이가 존재할때 "단어 쌍 관계로 정의"한다.

우리가 흔히 모든 경우가 허용되는데 일반적으로 사용되는 '*' 를 이용하여 주어진 단어 리스트에 대하여 "쌍"의 관계가 성립하는지 확인하는데 활용하자.

 

아이디어를 코드화하면 다음과 같다.

(※ 단어를 그래프 자료구조로 만드는 과정에서 n의 시간복잡도가 발생한다.)

neighbor = collections.defaultdict(list)
wordList.append(beginWord)

for word in wordList:
    for j in range(len(word)):

        #O(n), n = 단어 길이
        pattern = word[:j] + "*" + word[j + 1:] 
        neighbor[pattern].append(word)

 

둘째, BFS 알고리즘을 활용한 탐색과정

주어진 문제의 궁극적인 목적은 Startword → Endword 까지의 최단 경로를 묻는 문제이다. 가중치가 1인 최단 경로를 구하는 과정이며 여기서 활용되는 알고리즘은 BFS 알고리즘이다.

 

아이디어를 코드화하면 다음과 같다.

(※ 단어 탐색 과정에서  n * m 의 시간복잡도가 발생한다. 여기서 n = 단어 길이, m = 탐색 경우의 수 이다.)

visit = set([beginWord])
q = deque([beginWord])
res = []

while q:

    for i in range(len(q)): # 3, (h,i,t)

        word = q.popleft() # q = "hit"
        return word

        if word == endWord:
            res.append(endWord)
            return len(res)

        for j in range(len(word)): # 3 (h,i,t)

            #O(n), n = 단어 길이, O(n^2)
            pattern = word[:j] + "*" + word[j+1:] # (* ,i, t) , (h * t), (h, i, *)

            #O(m), m = 탐색 경우의 수, O(m*n^2)
            for neiWord in neighbor[pattern]: # (h, * , t) = (h, o ,t)
                if neiWord not in visit:
                    visit.add(neiWord)
                    q.append(neiWord)

    res.append(word)

 

---

 

Solution

전체 풀이코드는 아래와 같다.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        if endWord not in wordList: #wordlist에 endword가 없다면 0 반환
            return 0

        neighbor = collections.defaultdict(list)
        wordList.append(beginWord)

        for word in wordList:
            for j in range(len(word)):
                #O(n), n = 단어 길이
                pattern = word[:j] + "*" + word[j + 1:] # 단어 쌍을 위한 자료 그래프화 
                neighbor[pattern].append(word)

        visit = set([beginWord])
        q = deque([beginWord])
        res = []

        while q:

            for i in range(len(q)): # 3, (h,i,t)

                word = q.popleft() # q = "hit"
                return word
                
                if word == endWord:
                    res.append(endWord)
                    return len(res)
                
                for j in range(len(word)): # 3 (h,i,t)

                    #O(n), n = 단어 길이, O(n^2)
                    pattern = word[:j] + "*" + word[j+1:] # (* ,i, t) , (h * t), (h, i, *)

                    #O(m), m = 탐색 경우의 수, O(m*n^2)
                    for neiWord in neighbor[pattern]: # (h, * , t) = (h, o ,t)
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            
            res.append(word)
        
        return 0 #endword까지 도달할 수 없다면 0 반환