127. Word Ladder.md

127. Word Ladder(Hard)

Algorithm 1 One direction BFS

• change list to set so its faster to look up if word is in the wordList.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        wordQ = deque()
        wordQ.append(beginWord)
        ans = 1
        beginWordLen = len(beginWord)
        while(wordQ):
            wordQSize = len(wordQ)
            for i in range(wordQSize):
                curStr = wordQ.popleft()
                if curStr == endWord:
                    return ans
                for j in range(beginWordLen):
                    # convert one letter to 24 letters.
                    for oneChar in range(ord('a'), ord('z')+1):
                        strList = list(curStr)
                        strList[j] = chr(oneChar)
                        curStr1 = "".join(strList)
                        if curStr1 in wordSet:
                            if curStr1 == endWord:
                                return ans + 1
                            wordSet.remove(curStr1)
                            wordQ.append(curStr1)
            ans += 1
        return 0