127. Word Ladder (Hard)

처음에 bfs와 딕셔너리 쓰면 되는 건 잘 알겠는데, 어떻게 한글자씩 다른 word를 탐방할지 고민스러웠다

for 문을 다 돌려서 딕셔너리에 넣고 비교하는 코드를 짰는데, 당연하게도 TLE 가 났고 ...

답은 fox 면 그 안에 fix, fux, xox 이런 걸 넣는 게 아니라

*ox : fox

f*x: fox

fo*: fox

이렇게 딕셔너리에 키랑 값을 저장하는 거였다

메모리는 많이 들겠지만 TLE 가 나지는 않을 것 같다

from collections import Counter, defaultdict, deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        v = {beginWord:True}
        dict = defaultdict(list)
        L = len(beginWord)

        for word in wordList:
            for i in range(L):
                maskedWord = (word[:i]+'*'+word[i+1:])
                dict[maskedWord].append (word)
        def bfs(x):
            q = deque()
            q.append((x, 1))
            while q:
                cx, cnt = q.popleft()
                for i in range(L):
                    midWord = (cx[:i]+'*'+cx[i+1:])
                    for w in dict[midWord]:
                        if w == endWord:
                            return cnt + 1
                        if w not in v:
                            q.append((w, cnt+1))
                            v[w] = True
            return 0
        return bfs(beginWord)