Word ladder using bi-directional 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.

Bi-directional 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. We 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 checked before by using variable visited (explained below). If not, we can 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 bi-directional BFS?

Bi-directional BFS improves time complexity of BFS from O(b^d) to O(b^d/2). However in this case, the variable visited is used, it is a data structure that holds the nodes (i.e. words in this case) that have been visited. It is a tactic to guarantee that each node should be visited once. The technique is called memoization.

We also use another technique to speed up. Before each round of checking, we check the size of startSet and endSet. If the size of startSet is larger than endSet, they switch. So that startSet is always the smaller one. This keeps the comparison minimum. The time complexity of word ladder using bi-directional bfs with memoization is O(s*n). s is the word length. n is number of steps.

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

JavaScript

Python

Output:
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
Big O-Notations of DFS and BFS

Comments are closed