리트코드(Leetcode)/Word_Ladder

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

Word Ladder - LeetCode

내 첫번째 코드이다. 시간복잡도는 word_length = L , size of list = M 이라 했을 때, Time Complexity 가 O(M^2 * L)이다. 

BFS를 잘 수행했다고 하는데, 계속해서 시간초과..... 단 1개만 다른 char를 찾을 수 있는 더 효율적인 방법을 찾아봐야겠습니다..

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
​
        queue = []
        queue.insert(0,[beginWord, 1])
        word_length = len(beginWord)
        
        while queue:
            current_word, length = queue.pop()
            
            if current_word == endWord:
                return length
            
            else:
                wordListCopy = wordList.copy()
                for word in wordListCopy:
                    same_letters = 0
                    for i in range(word_length):
                        if word[i] == current_word[i]:
                            same_letters += 1
                    if same_letters == word_length -1:
                        queue.insert(0,[word, length+1])
                        wordList.remove(word)         
        return 0

 

다음은 통과가 가능한 문제풀이입니다. 

이건 시간 복잡도가 O(L * M)입니다.
시간복잡도를 줄이기 위한 핵심으로 아래 두 가지를 동시에 고려해야 합니다.

1. BFS(이건 필수)
2. 탐색 단어 시점에서 한가지만 다른 단어, 즉 간선으로 연결된 다음 노드를 어떻게 빨리 찾느냐에 대한 고려도 함께 할 것 (해쉬 자료 구조 사용)

1번을 위해선 Queue를 사용했고, 2번을 위해 all_mutable_word 라는 dict 자료형을 이용했습니다.
key 값으로 한글자만 ‘*’값으로 두었고, 이에 대해 해당 *을 제외한 변형이 가능한 단어의 리스트를 배열로 넣었습니다.
이렇게 된다면, 나의 탐색중인 단어가 “abc”일 때, abc 중 “*bc”, “a*c”, “ab*“, 를 키값으로 매칭되는 변형이 가능한 단어를 바로 value로서 찾을 수 있습니다. 이렇게 변형가능한 단어를 찾는 과정에서 시간복잡도는 O(1)이므로 시간을 아낄 수 있는 것입니다.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        queue = []
        queue.insert(0,[beginWord, 1])
        word_length = len(beginWord)
        visited_dicts = collections.defaultdict(bool)
        all_mutable_words = collections.defaultdict(list)
​
        for word in wordList:
            visited_dicts[word] = False
            for i in range(word_length):
                all_mutable_words[word[:i]+'*'+word[i+1:]].append(word)
​
        while queue:
            current_word, length = queue.pop()
            visited_dicts[current_word] = True
            
            if current_word == endWord:
                return length 
​
            for i in range(word_length):
                for next_word in all_mutable_words[current_word[:i]+'*'+current_word[i+1:]]:
                    if  visited_dicts[next_word] == False:
                        queue.insert(0, [next_word, length+1])
​
        return 0