字梯

from collections import deque, defaultdict
def ladder_length_opt(beginWord, endWord, wordList):
    if endWord not in wordList: return 0
    nei = defaultdict(list)
    wordList.append(beginWord)
    for word in wordList:
        for j in range(len(word)):
            pattern = word[:j] + "*" + word[j + 1 :]
            nei[pattern].append(word)
    visit = {beginWord}
    q = deque([beginWord])
    res = 1
    while q:
        for i in range(len(q)):
            word = q.popleft()
            if word == endWord: return res
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                for neighbor in nei[pattern]:
                    if neighbor not in visit:
                        visit.add(neighbor)
                        q.append(neighbor)
        res += 1
    return 0

def ladder_length_brute(beginWord, endWord, wordList):
    if endWord not in wordList: return 0
    def is_diff_one(w1, w2):
        diff = 0
        for i in range(len(w1)):
            if w1[i] != w2[i]: diff += 1
        return diff == 1
    q = [(beginWord, 1)]
    visit = {beginWord}
    while q:
        word, dist = q.pop(0)
        if word == endWord: return dist
        for w in wordList:
            if w not in visit and is_diff_one(word, w):
                visit.add(w)
                q.append((w, dist + 1))
    return 0