Word Ladder

word_ladder_lc.py

from collections import deque


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordLength = len(beginWord)
        wordDict = {}
        for i in range(len(wordList)):
            wordDict[wordList[i]] = i

        def is1hamming(str1, str2):
            chg = 0
            for i in range(len(str1)):
                if str1[i] != str2[i]:
                    chg += 1
                if chg == 2:
                    return False
            return chg == 1
            

        beginNodes = []
        ewInWL = False
        ewIdx = -1
        for i in range(0, len(wordList)):
            if wordList[i] == endWord:
                ewInWL = True
                ewIdx = i
            
            if is1hamming(wordList[i], beginWord):
                beginNodes.append(i)

        if not ewInWL or len(beginNodes) == 0:
            return 0
        

        visited = set()
        q = deque()
        for x in beginNodes:
            q.append((1, x))
            visited.add(x)

        while q:
            depth, curNode = q.popleft()
            if curNode == ewIdx:
                return depth+1
            
            for i in range(wordLength):
                word = list(wordList[curNode])

                tmp = word[i]

                for char in ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']:
                    if char == tmp:
                        continue
                    word[i] = char
                    perm = "".join(word)

                    if perm in wordDict and wordDict[perm] not in visited:
                        q.append((depth+1, wordDict[perm]))
                        visited.add(wordDict[perm])

        return 0