Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

OR

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  • only one letter can be changed at a time and
  • each intermediate word must exist in the dictionary.

Examples

Example 1:

1
2
3
4
5

Input:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output:
 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

1
2
3
4
5

Input:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output:
 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Note that we account for the length of the transformation path instead of the number of transformation itself.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution

Method 1 - BFS

To find the shortest transformation sequence, we can perform a Breadth-First Search (BFS). BFS is suitable here as it explores all possible transformations level by level, ensuring that the first time we reach the endWord, we have found the shortest path.

Approach

  1. Initial Checks: Ensure endWord is in the wordList. If not, return 0.
  2. BFS Initialization: Use a queue to store the current word and its transformation depth. Begin with the beginWord and a depth of 1.
  3. BFS Execution:
    • For each word, generate all possible single-letter transformations.
    • For each transformation, if it matches the endWord, return the current depth + 1.
    • If the transformation is in wordList, add it to the queue and remove it from wordList to prevent revisiting.
  4. Return: If the queue is exhausted without finding the endWord, return 0.
graph TD;
A["hit"] --> B["a̲it"]:::nonAns & C["b̲it"]:::nonAns & D["..."]:::nonAns & E["z̲it"]:::nonAns & F["ha̲t"]:::nonAns & G["..."]:::nonAns & H["ho̲t"]:::ans & I["..."]:::nonAns & J["hz̲t"]:::nonAns & K["..."]:::nonAns & L["hiz̲"]:::nonAns
H ---> P["..."]:::nonAns & Q["d̲ot"]:::ans & R["..."]:::nonAns

classDef ans fill:#fc6b03
classDef nonAns stroke-width:2px, stroke-dasharray: 5 5, font-size:10pt

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int ans = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                if (word.equals(endWord)) return ans;

                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char originalChar = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (chars[j] == c) continue;
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                    chars[j] = originalChar;
                }
            }
            ans++;
        }
        return 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

        queue = deque([beginWord])
        ans: int = 1

        while queue:
            size = len(queue)
            for _ in range(size):
                word = queue.popleft()
                if word == endWord:
                    return ans
                
                for i in range(len(word)):
                    original_char = word[i]
                    for c in range(26):
                        new_char = chr(ord('a') + c)
                        if word[i] == new_char:
                            continue
                        new_word = word[:i] + new_char + word[i+1:]
                        if new_word in wordSet:
                            queue.append(new_word)
                            wordSet.remove(new_word)

            ans += 1
        return 0

Complexity

  • ⏰ Time complexity: O(M*N) where M is the length of each word and N is the total number of words in the wordList, because generating all possible transformations and comparing them takes linear time.
  • 🧺 Space complexity: O(M*N) due to the space needed for the queue and the intermediate transformations.