127. Word Ladder (Hash Table, String, Breadth-First Search)

링크 - https://leetcode.com/problems/word-ladder/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

먼저 word_combo를 사용해서 word[:i] + "*" + word[i+1:]의 단어들을 저장해놓는다. 그다음 bfs를 통해서 단어를 찾아 나가면 된다.

Code

from collections import defaultdict


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

        if (
            endWord not in wordList
            or not endWord
            or not beginWord
            or not wordList
        ):
            return 0

        # Since all words are of same length.
        L = len(beginWord)

        # Dictionary to hold combination of words that can be formed,
        # from any given word. By changing one letter at a time.
        all_combo_dict = defaultdict(list)
        for word in wordList:
            for i in range(L):
                # Key is the generic word
                # Value is a list of words which have the same intermediate generic word.
                all_combo_dict[word[:i] + "*" + word[i + 1 :]].append(word)

        # Queue for BFS
        queue = collections.deque([(beginWord, 1)])
        # Visited to make sure we don't repeat processing same word.
        visited = {beginWord: True}
        while queue:
            current_word, level = queue.popleft()
            for i in range(L):
                # Intermediate words for current word
                intermediate_word = (
                    current_word[:i] + "*" + current_word[i + 1 :]
                )

                # Next states are all the words which share the same intermediate state.
                for word in all_combo_dict[intermediate_word]:
                    # If at any point if we find what we are looking for
                    # i.e. the end word - we can return with the answer.
                    if word == endWord:
                        return level + 1
                    # Otherwise, add it to the BFS Queue. Also mark it visited
                    if word not in visited:
                        visited[word] = True
                        queue.append((word, level + 1))
                all_combo_dict[intermediate_word] = []
        return 0

Complexity

Time Complexity: O(M^2 * N) M은 각 단어들의 길이이고, N은 wordList에 있는 단어 개수이다.

Space Complexity: O(M^2 * N)