127. Word Ladder - Detailed Explanation

Problem Statement

You are given two words: beginWord and endWord, and a dictionary wordList (a list of allowed words). Your goal is to transform beginWord into endWord by changing one letter at a time. Each intermediate word must exist in the wordList.

Rules:

• Only one letter can be changed at a time.
• Each transformed word must exist in the word list.
• Return the length of the shortest transformation sequence (i.e. the number of words in the sequence, including the beginWord and endWord).
• If no such transformation sequence exists, return 0.

Example 1:

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

Example 2:

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

Hints to Solve the Problem

1. Graph Interpretation:
   Think of each word as a node in a graph. Two nodes are connected if they differ by exactly one letter.

2. Breadth-First Search (BFS):
   Since you need the shortest transformation sequence, BFS is ideal. Starting from beginWord, explore all words one letter away, then all words two letters away, and so on until you reach endWord.

3. Preprocessing – Intermediate States:
   To speed up neighbor searches, consider generating intermediate states. For example, for the word "hot", replace each letter with a wildcard character (e.g. "*ot", "h*t", "ho*"). Map these intermediate states to all words in the list that match them. This lets you quickly find all adjacent words.

4. Avoid Revisiting Nodes:
   Use a visited set to ensure that you don’t process the same word more than once.

Approaches

Approach 1: Brute Force (Inefficient)

Idea:

• For each word, try changing every letter (26 possibilities per position) and check if the new word is in the wordList.
• Repeat this process (using recursion or BFS) until you reach the endWord.
• The brute force approach would try all possibilities without precomputation and will quickly become inefficient for larger word lists.

Drawbacks:

• Time complexity explodes because for every word you try up to 26 × (word length) transformations.
• Checking membership in the wordList every time without preprocessing is costly.

Approach 2: Optimal BFS with Preprocessing

Idea:

1. Preprocess the wordList:
   • For each word in the wordList, create all possible intermediate states by replacing each letter with a wildcard (e.g., for "hot", generate "*ot", "h*t", "ho*").
   • Use a dictionary to map each intermediate state to the list of words that have that form.
2. BFS Traversal:
   • Start from beginWord and use BFS to explore neighbors.
   • For each word popped from the BFS queue, generate its intermediate states and look up all adjacent words from the preprocessed dictionary.
   • If an adjacent word is the endWord, return the current level (or depth) + 1.
   • Mark words as visited once they are enqueued to avoid cycles.

Why It Works:

• BFS guarantees the shortest path in an unweighted graph.
• Preprocessing reduces the cost of finding neighbors from O(26*L) to O(1) average lookup per intermediate state.

Step-by-Step Walkthrough (Using BFS with Preprocessing)

Consider beginWord = "hit", endWord = "cog", and wordList = ["hot","dot","dog","lot","log","cog"].

1. Preprocessing:

   • For "hot" generate: "*ot", "h*t", "ho*".
   • Do similar for all words in the list.
     The dictionary might look like:

   {
     "*ot": ["hot", "dot", "lot"],
     "h*t": ["hot"],
     "ho*": ["hot"],
     "d*t": ["dot"],
     "do*": ["dot", "dog"],
     "*og": ["dog", "log", "cog"],
     "d*g": ["dog"],
     "l*t": ["lot"],
     "lo*": ["lot", "log"],
     "l*g": ["log"],
     "c*g": ["cog"],
     "co*": ["cog"]
   }
   

2. BFS Start:

   • Start at "hit" (level 1).
   • Generate intermediate states for "hit": "*it", "h*t", "hi*".
   • From the dictionary, "h*t" maps to ["hot"].

3. BFS Level 2:

   • Enqueue "hot" and mark as visited.
   • Next, process "hot": its intermediate states are "*ot", "h*t", "ho*".
   • These map to neighbors: "dot", "lot" (from "*ot") and "hot" itself (from "h*t" and "ho*" but already visited).
   • Enqueue "dot" and "lot".

4. BFS Level 3:

   • Process "dot": intermediate states yield neighbors like "dog".
   • Process "lot": intermediate states yield neighbors like "log".
   • Enqueue "dog" and "log".

5. BFS Level 4:

   • Process "dog": one of its intermediate states is "*og", which maps to "cog".
   • When "cog" is reached, the level is 5.

Thus, the shortest transformation is 5.