Word Ladder

Lessons learned: Breadth First Search

Question: 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

Each intermediate word must exist in the dictionary. For example, given

  • Start: “hot”

  • End: “log”

  • Dict: [“hit”, “fot”, “fog”, “cot”, “cog”]

As one shortest transformation is "hot" ->"cot" ->"cog" ->"log", the program should return its length 4.

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

Solution

Approach 1: Brute Force

To solve the problem using brute force, we can start from the start word, change one character each time and if the resulting word is in the dict, we can continue with the replaced word until start == end.

See Approach 1

This solution is not good enough. We do not guarantee that we’re finding the shortest path, we are just finding any valid path from start to end.

  • Input: "d", "f", ["d","e","f"]

  • Output: 3

  • Expected: 2

Approach 2: Breadth First Search

So we realize that this looks like a tree searching problem for which breadth first guarantees the optimal solution.

Assuming we have some words in the dictionary, and the start is "hit", we can use two queues to traverse the tree, one stores the nodes, the other stores the step numbers.

See Approach 2

We’re done!


Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.

Subscribe to get full access to the newsletter. Never miss an update.