Word Ladder

Given two words (beginWordandendWord), and a dictionary's word list, find the length of shortest transformation sequence frombeginWordtoendWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord="hit"
endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]

As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Solution:

Time Complexity: O(n) where constant is 26

BFS approach.

1 queue for storing words to be processed.

1 set to track visited words in word list to avoid doing duplicate work.

1 temporary queue.

For each word either startWord or word in wordList during transformation finding, swap each letter in all positions with 26 letters to find next valid word to store in temp queue. Thus O(26) per each iteration, there should be n iterations where n is the length of the wordList

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """

        # bfs approach
        wordList = set(wordList)
        visited = set() # to avoid going back to visited words
        q = [beginWord]
        level = 1

        while q:
            newQ = []
            for word in q:
                # swap each letter of word to create new word
                for i in range(len(word)):
                    for letter in "abcdefghijklmnopqrstuvwxyz":
                        newWord = word[:i] + letter + word[i + 1:]

                        if newWord in wordList and newWord not in visited:
                            if newWord == endWord:
                                level += 1
                                return level
                            newQ.append(newWord)
                            visited.add(newWord)
            q = newQ
            level += 1

        return 0