Word Morph

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Word Morph

You are transforming begin_word into end_word one letter at a time, and every intermediate word must appear in word_list. Each step may change exactly one letter.

Return the number of words in the shortest transformation sequence (counting both endpoints), or 0 if no sequence exists.

def ladder_length(begin_word, end_word, word_list):
    pass

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 30-45 mins
• 🛠️ Topics: Graphs, Breadth-First Search (BFS), Shortest Path

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What counts as a valid transformation step?

  • A: Changing exactly one letter of the current word, where the resulting word must appear in word_list.

• Q: Does begin_word need to be in word_list? Does end_word?

  • A: begin_word does not need to be in word_list because it is the starting point, but end_word must be in word_list — otherwise no valid sequence can end there, and we return 0.

• Q: What exactly are we counting in the answer?

  • A: The number of words in the shortest sequence, counting both begin_word and end_word. For example, "hit" -> "hot" -> "dot" -> "dog" -> "cog" counts as 5.

HAPPY CASE
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
Explanation: One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which contains 5 words.

EDGE CASE
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log"]
Output: 0
Explanation: "cog" is not in the word list, so no valid transformation sequence exists.

Input: begin_word = "hot", end_word = "dog", word_list = ["hot", "dog"]
Output: 0
Explanation: "hot" and "dog" differ in two letters, and no intermediate word bridges them, so no sequence exists.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Shortest Path Problems on Implicit Graphs, we can consider the following approaches:

• BFS (Breadth-First Search): Treat each word as a node and connect words that differ by exactly one letter. BFS explores the graph level by level, so the first time we reach end_word we are guaranteed to have used the fewest possible steps.
• DFS (Depth-First Search): Can find a path, but not necessarily the shortest one, so it is a poor fit here.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Model the words as an implicit graph: two words are neighbors if they differ by exactly one letter. Run BFS starting from begin_word, tracking the sequence length (in words) at each level. To find a word's neighbors efficiently, substitute each letter position with every letter a-z and check membership in a set built from word_list. The first time BFS dequeues end_word, return its level.

1) Convert word_list into a set for O(1) lookups. If end_word is not in the set, return 0.
2) Initialize a queue with (begin_word, 1), since the sequence starts with 1 word.
3) Initialize a visited set containing begin_word.
4) While the queue is not empty:
   a) Dequeue (word, length).
   b) If word equals end_word, return length.
   c) For each position in word and each letter a-z, build a candidate neighbor.
   d) If the neighbor is in the word set and not visited, mark it visited and enqueue (neighbor, length + 1).
5) If BFS finishes without reaching end_word, return 0.

⚠️ Common Mistakes

• Using DFS instead of BFS, which finds a path but not necessarily the shortest one.
• Forgetting to check that end_word is in word_list before searching, wasting time on an impossible search.
• Not marking words as visited (or marking them too late, when dequeued instead of when enqueued), causing repeated work or infinite loops.
• Comparing every pair of words in the list to build the graph (O(N^2 * L)), instead of generating one-letter variations against a set.
• Returning the number of steps (edges) instead of the number of words in the sequence — both endpoints count.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def ladder_length(begin_word, end_word, word_list):
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    queue = deque([(begin_word, 1)])  # (current word, sequence length so far)
    visited = {begin_word}

    while queue:
        word, length = queue.popleft()
        if word == end_word:
            return length
        # Generate every word one letter away from the current word
        for i in range(len(word)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                neighbor = word[:i] + c + word[i + 1:]
                if neighbor in word_set and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, length + 1))

    return 0

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log", "cog"]

  • Level 1: dequeue ("hit", 1); enqueue "hot".
  • Level 2: dequeue ("hot", 2); enqueue "dot" and "lot".
  • Level 3: dequeue ("dot", 3) and ("lot", 3); enqueue "dog" and "log".
  • Level 4: dequeue ("dog", 4) and ("log", 4); enqueue "cog".
  • Level 5: dequeue ("cog", 5); it matches end_word.
  • Output: 5

• Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log"]

  • "cog" is not in the word set, so we return immediately.
  • Output: 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of words in word_list and L is the length of each word.

• Time Complexity: O(N * L^2) because BFS visits each word at most once, and for each word we generate L * 26 candidate neighbors, where each candidate takes O(L) time to build and hash.
• Space Complexity: O(N * L) for the word set, the visited set, and the BFS queue, each of which holds up to N words of length L.