import collections
import string
class Solution(object):
    def ladderLength(self, start, end, arr):
        arr = set(arr)  # avoid TLE
        q = collections.deque([(start, 1)])
        visted = set()
        alpha = string.ascii_lowercase  # 'abcd...z'
        while q:
            word, length = q.popleft()
            if word == end:
                return length

            for i in range(len(word)):
                for ch in alpha:
                    new_word = word[:i] + ch + word[i + 1:]
                    if new_word in arr and new_word not in visted:
                        q.append((new_word, length + 1))
                        visted.add(new_word)
        return 0
"""
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        def isoneletter(word1,word2):
            count=0
            n=len(word1)
            for i in range(n):
                if word1[i]!=word2[i]:
                    if count==0:
                        count=1
                    else:
                        return False
            return True

        if len(wordList)==0:
            return
        if endWord not in wordList:
            return 0
        wordList.append(beginWord)
        numtoletter={}
        lettertonum={}
        count=0
        for item in wordList:
            numtoletter[count]=item
            lettertonum[item]=count
            count+=1
        dp=[[count+1 for i in range(count)]for j in range(count)]
        for i in range(count):
            for j in range(count):
                if i==j:
                    dp[i][j] = dp[j][i] = 0
                else:
                    word1=numtoletter[i]
                    word2=numtoletter[j]
                    index=isoneletter(word1,word2)
                    if index==True:
                        dp[i][j]=dp[j][i]=1
        for i in range(count):
            for j in range(count):
                for k in range(count):
                    if dp[i][j]>dp[i][k]+dp[k][j]:
                        dp[i][j]=dp[j][i]=dp[i][k]+dp[k][j]
        index1=lettertonum[beginWord]
        index2=lettertonum[endWord]
        if dp[index1][index2]!=count+1:
            return dp[index1][index2]+1
        else:
            return 0
"""
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
s=Solution()
print(s.ladderLength(beginWord,endWord,wordList))