127. Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that:

• The first word in the sequence is beginWord.
• The last word in the sequence is endWord.
• Only one letter is different between each adjacent pair of words in the sequence.
• Every word in the sequence is in wordList.

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

이건 문제 자체가 창의력 대장님이 만드신 문제 같음..

내 머리로는 안된다는 뜻~

Solution 1: Runtime: 124 ms - 76.73% / Memory Usage: 17.9 MB - 28.52%

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # endWord 가 wordList 에 없거나 / word 가 하나라도 None 일 경우 => return 0
        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0
        
        L = len(beginWord)
        all_combo_dict = defaultdict(list)
        
        # wordList 의 word 들을 beginWord 길이만큼 한글자씩 * 처리한 all_combo_dict 에 append
        # ex) word: hot, len(beginWord): 3 => *ot, h*t, ho*
        for word in wordList:
            for i in range(L):
                all_combo_dict[word[:i] + "*" + word[i+1:]].append(word) 
        
        queue = deque([(beginWord, 1)])
        visited = set()	# 이미 본 word 는 사용 X 위해서
        visited.add(beginWord)
        
        while queue:
            current_word, level = queue.popleft()
            for i in range(L):
                intermediate_word = current_word[:i] + "*" + current_word[i+1:]
                # h*t 처럼 intermediate_word 에 속하는 word 들을 다 꺼내와서 endWord 인지 한글자 다른 word 인지 확인
                for word in all_combo_dict[intermediate_word]:
                    if word == endWord:
                        return level + 1
                    # 안 쓴 word 중에 찾았으면 '다음 레벨에서 또 비슷한 애 찾으세요' 하고 queue 에 append
                    if word not in visited:
                        visited.add(word)
                        queue.append((word, level + 1))
                        
        return 0

https://leetcode.com/problems/word-ladder/discuss/346920/Python3-Breadth-first-search

beginWord 부터 한글자씩 다른 word 들에게 level 부여

그냥 천재같고 그렇읍니다..^^