< Back




127. Word Ladder

Given a beginning word, an ending word, and a word list, we're asked to determine the number of
words we can string together to transform the beginning word to the ending word, with the constraint
that the pairs of words in this string of words differ by 1 character.

We already know, given the requirement to find the shortest path, that we're going to use BFS. The
most annoying trick is to great a graph of candidate word combinations based on our 1 character
constraint. We do so by processing all words in the word list and using a wildcard character at
each index as the key for the node in the graph. The adjacency list for each node is a list of words
that can be reached from the key word by changing one character.

Once the graph is completed, we conduct BFS like always and return the length of the shortest path
when we see the ending word.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
          if endWord not in wordList or not endWord or not wordList or not beginWord:
              return 0

          n = len(beginWord)
          combos = defaultdict(list)
          for word in wordList:
              for i in range(n):
                  combos[word[:i] + "*" + word[i + 1 :]].append(word)

          seen = {beginWord}
          queue = [(beginWord, 1)]

          while queue:
              curr_queue, queue = queue, []

              for cword, steps in curr_queue:
                  for i in range(n):
                      for word in combos[cword[:i] + "*" + cword[i + 1 :]]:
                          if word == endWord:
                              return steps + 1

                          if word not in seen:
                              seen.add(word)
                              queue.append((word, steps + 1))

          return 0


_ Time Complexity:

  O(m^2 * n) - Where m is the length of the word and n is the number of words.

_ Space Complexity:

  O(m^2 * n) - Where m is the length of the word and n is the number of words.