Bi-directional BFS and examples – Code

A bi-directional search is to start search from two ends simultaneously. The drive of this is to make the search efficient. BFS is short for Breadth First Search. The search starts from the source node. Then explores all its adjacent nodes before going to the next level adjacent nodes. The bi-directional BFS combines these two techniques to solve problems and improve performance.

Let’s look at a popular interview question Word ladder first. It asks to return the number of steps to convert one string to another by changing one letter at a time. The intermediate words should be in dictionary too. The intuitive solution is using BFS. It starts from original word, and changes one letter at a time. Until it finds the destination word. Now let’s apply bi-directional BFS. We start from both original word and destination word. The search can meet in the middle. It cuts the search time by half.

Open lock is a variation of word ladder problem. In open lock, instead of letters, lock is binary number, either 0 or 1. We can apply the same techniques. Below are the solution to solve both by using bi-directional BFS.


1. Word ladder

Amazon Interview Question:
Given two strings s and t, and a dictionary D, transform s to t by changing one letter at a time, Each transformed word must exist in the dictionary. Find the length of shortest transformation. Return 0 if there is no such transformation sequence.
Example
Input: s = “cat”, t = “dog”, dictionary = [“cat”, “bat”, “bet”, “bot”, “bog”, “dog”]
Output: 5, As one shortest transformation is [cat->bat-> bot-> bog-> dog]

Java Code:

Output:
Dictinary: [cat, bat, bet, bot, bog, dog]
Start: ‘cat’, end: ‘dog’
Length of word ladder: 5

O Notation:
Time complexity: O(s * d)
Space complexity: O(s * d) for storing the intermediate data
s is string length, d is number of words in dictionary.


2. Open lock

Google Interview Question:
There is an init state, end state and safe states. If it is possible to go from the init state to the end state (using the safe states), do so in minimum number of iterations and return ‘disarm’. If not possible, return ‘run’.
Values for a state can either be a ‘0’ or a ‘1’. Only one value of the state can be changed at a time.
Each transformed state must exist in the safe states.
Examples as below:
init: 000
end: 111
safe: 001 010 100 011 111 101
return: disarm [ 000 –> 001 –> 101 –> 111 ]
init: 00
end: 11
return: 00 11
return: run

Java Code:

Output:
number of steps: 3
disarm

O Notation:
Time complexity: O(m * n)
Space complexity: O(n) for storing the intermediate data
n is the length of start word, m is number of words in the dictionary


Download BiDirectionalBFS.zip
Java Coding Interview Pocket Book (2nd Edition)
Coding interview youtuble series (YouTube)

Comments are closed