Lessons learned: Breadth First Search
|Sameer Khoja||Feb 14|
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
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.
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.
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"]
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.
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.