Word ladder using bidirectional BFS – time complexity explained

Word ladder is to find the number of steps to convert one string to another by changing one letter at a time. The intermediate words should be valid and can be found in pre-defined dictionary. The intuitive solution is using breadth first search (BFS). It starts from the original word, and changes one letter at a time, keeps doing until it finds the target word. A better solution of word ladder is using Bi-directional BFS.

Bidirectional BFS starts from both original word and target word. The search can meet in the middle. It cuts the search time by half. In the implementation, we maintain two sets startSet and endSet. The startSet holds all words changed from the original word, with one character change at a time. The endSet holds all words from the target word. Initially they only hold the original word and the target word respectively.

In the loop, we check each word in the startSet. Change one character at a time to create a new word next. Check whether the next is in the endSet. If not, first check whether this word is a valid word in the dictionary. If it is, check whether the word had been used before by using variable visited. visited guarantees that intermediate words occur once. If not, add it to the startSet, and start the next round of checking. If the next is in the endSet, the target is found. We reach the goal and the program returns.

What is time complexity of word ladder using bidirectional BFS?

The time complexity of BFS without memoization is O(b^d). b is branch factor, d is distance from start to end. Bidirectional BFS improves time complexity of BFS to O(b^(d/2)). So the time complexity is still exponential. In word ladder using bidirectional BFS, due to variable visited used for memoization, the time complexity is O(s*n). s is the word length. n is number of steps. The time complexity is quadratic. This is better than exponential.

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.
Input: s = “cat”, t = “dog”, dictionary = [“cat”, “bat”, “bet”, “bot”, “bog”, “dog”]
Output: 5, As one shortest transformation is [cat->bat-> bot-> bog-> dog]




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

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

Download WordLadder.java
Download WordLadder.js
Download WordLadder.py

Comments are closed