Word Ladder ( Doublets / Word-links / Word golf )
Given two words, startWord and endWord, and a dictionary, find the length of shortest transformation sequence from startWord to endWord.
Rules:
1. Only one letter can be changed at a time.
2. Each intermediate word must exist in the dictionary.
Input
startWord = CAT
endWord = DOG
dictionary = CAT, BAT, COT, COG, COW, RAT, BUT, CUT, DOG, WEB
Output
One shortest transformation is CAT –> COT –> COG –> DOG.
the program should return Path and its length 4.
Let's look at few more example and better understand problem statement.
Solution
There are 2 approach to solve this problem,
1. Breadth First approach
2. Depth First approach
Breadth First approach
In this approach, we will go Iteration by Iteration from CAT to DOG,
Our approach will be similar like shown in picture below,
We will take a Queue, in which we will store our path from CAT to DOG.
We don't know the complete path from CAT to DOG, so we will start creating it step by step and put it in Queue until we get the complete path.
First Iteration:
Initially, we only know one word "CAT" that is startWord of our solution, So, put that in Queue.
Now, pick path that exist in Queue (path that we found till now) and check,
is endWord we are looking for is reached?
If not then check all words in dictionary and compare it with CAT, collect all words, which have one letter difference among them.
We will get 4 possible path, which may lead us to solution, So put all solutions in Queue.
[CAT, COT]
[CAT, BAT]
[CAT, CUT]
[CAT, RAT]
Now, pick all intermediate paths, one by one from Queue,
1. [CAT, COT],
check, is the endWord we are looking for is reached that is compare COT with DOG?
If not then Check all words in dictionary and compare it with COT, collect all words, which
have one letter difference among them and put all them in Queue, we will get,
[CAT, COT, COG]
[CAT, COT, COW]
2. [CAT, BAT],
check, is the endWord we are looking for is reached that is compare BAT with DOG?
If not then Check all words in dictionary and compare it with BAT, collect all words, which
have one letter difference among them and put all them in Queue, we will get,
[CAT, BAT, BUT]
3. [CAT, CUT],
check, is the endWord we are looking for is reached that is compare CUT with DOG?
If not then Check all words in dictionary and compare it with CUT, collect all words, which
have one letter difference among them and put all them in Queue, we will get,
No Path exist.
3. [CAT, RAT],
check, is the endWord we are looking for is reached that is compare RAT with DOG?
If not then Check all words in dictionary and compare it with RAT, collect all words, which
have one letter difference among them and put all them in Queue, we will get,
No Path exist.
Our Third iteration is complete
Forth Iteration:
In this iteration, pick all intermediate paths one by one that we found in 3rd iteration and try to get our destination word.
Repeat the steps until we find the complete path till endWord.
Queue status will be,
All iterations will look as shown below,
In above example, we will get complete path in last iteration.
So this was Breadth First approach, where all words at same levels are collected first, that is all words with one letter difference are collected in Queue, and then each paths are checked for next level words until we found the endWord.
Depth First approach
In this approach, instead of finding all the words which have difference of one character in them,
we will find one word and start exploring that new word till we find the path containing endWord.
If that path doesn't lead us to solution then we will rollback to point where we can start new path and start exploring new path.
So lets understand it with the help of example,
In BFS, what first we did is, queue all the words which have one character difference compare to startWord CAT, which result in
[CAT, COT] (start looking for solution from this path first)
[CAT, BAT] (If no solution exist from above path, then only pick this path and start exploring)
[CAT, CUT] (If no solution exist from above path, then only pick this path and start exploring)
[CAT, RAT] (If no solution exist from above path, then only pick this path and start exploring)
then we picked first path [CAT, COT] and repeated the process
In DFS, instead of finding all the words which have one character difference compare to startWord CAT, we will only find one word, say [CAT, COT] and once we got atleast a single word, which differs by one character, then we will start exploring path with new word COT here.
We will get [CAT, COT, COG], now we will start exploring path with new word COG here.
We will get [CAT, COT, COG, DOG], last word DOG matched with our endWord,
So stop the process here.
So, If you observe, we got the solution by only exploring one path.
If say we doesn't got the solution, then we will backtrack to point where new path can be started and start exploring new path.
In DFS, If we got the solution by just exploring single path, we can't say that path will be shortest because there might exist some other path which is shortest.
So, In DFS, for finding the shortest path from startWord to endWord, we have to first find all the possible paths and then decide the shortest path among them based on size.
Word Ladder java program.
Ladder.java
package javabypatel;
class Ladder{
private List<String> path; //For storing path
private String lastWord; //For storing last word of path
private int length; //Length of the path.
public Ladder(List<String> path) {
this.path=path;
}
public Ladder(List<String> path, int length, String lastWord) {
this.path=path;
this.length=length;
this.lastWord=lastWord;
}
public List<String> getPath() {
return path;
}
public int getLength() {
return length;
}
public String getLastWord() {
return lastWord;
}
public void setPath(List<String> path) {
this.path = path;
}
public void setLength(int length) {
this.length = length;
}
}
WordLadderShortestPath.java
package javabypatel;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class WordLadderShortestPath {
public static void main(String[] args) {
Set<String> dictionary = new HashSet<String>();
dictionary.add("CAT");
dictionary.add("BAT");
dictionary.add("COT");
dictionary.add("COG");
dictionary.add("COW");
dictionary.add("RAT");
dictionary.add("BUT");
dictionary.add("CUT");
dictionary.add("DOG");
dictionary.add("WEB");
String startWord = "CAT";
String endWord = "DOG";
Ladder result = getShortestTransformationIterative(startWord, endWord, dictionary);
//Ladder result = getShortestTransformationRecursive(startWord, endWord, dictionary);
if(result!=null){
System.out.println("Length is "+result.getLength() + " and path is :"+ result.getPath());
}else{
System.out.println("No Path Found");
}
}
private static Ladder getShortestTransformationIterative(String startWord, String endWord, Set<String> dictionary){
if(dictionary.contains(startWord) && dictionary.contains(endWord)){
List<String> path = new LinkedList<String>();
path.add(startWord);
//All intermediate paths are stored in queue.
Queue<Ladder> queue = new LinkedList<Ladder>();
queue.add(new Ladder(path, 1, startWord));
//We took the startWord in consideration, So remove it from dictionary, otherwise we might pick it again.
dictionary.remove(startWord);
//Iterate till queue is not empty or endWord is found in Path.
while(!queue.isEmpty() && !queue.peek().equals(endWord)){
Ladder ladder = queue.remove();
if(endWord.equals(ladder.getLastWord())){
return ladder;
}
Iterator<String> i = dictionary.iterator();
while (i.hasNext()) {
String string = i.next();
if(differByOne(string, ladder.getLastWord())){
List<String> list = new LinkedList<String>(ladder.getPath());
list.add(string);
//If the words differ by one then dump it in Queue for later processsing.
queue.add(new Ladder(list, ladder.getLength()+1, string));
//Once the word is picked in path, we don't need that word again, So remove it from dictionary.
i.remove();
}
}
}
//Check is done to see, on what condition above loop break,
//if break because of Queue is empty then we didn't got any path till endWord.
//If break because of endWord matched, then we got the Path and return the path from head of Queue.
if(!queue.isEmpty()){
return queue.peek();
}
}
return null;
}
private static Ladder getShortestTransformationRecursive(String startWord, String endWord, Set<String> dictionary){
//All Paths from startWord to endWord will be stored in "allPath"
LinkedList<Ladder> allPath = new LinkedList<Ladder>();
// Shortest path will be stored in "shortestPath"
Ladder shortestPath = new Ladder(null);
List<String> path = new LinkedList<String>();
path.add(startWord);
recursiveHelperShortest(startWord, endWord, dictionary, new Ladder(path, 1, startWord), allPath, shortestPath);
return shortestPath;
}
private static void recursiveHelperShortest(String startWord, String endWord, Set<String> dictionary, Ladder ladder, LinkedList<Ladder> allPath, Ladder shortestPath){
if(ladder.getLastWord().equals(endWord)){
// For storing all paths
allPath.add(new Ladder(new LinkedList<String>(ladder.getPath())));
//For storing the shortest path from among all paths available
if(shortestPath.getPath()==null || shortestPath.getPath().size()>ladder.getPath().size()){
shortestPath.setPath(new LinkedList<String>(ladder.getPath()));
shortestPath.setLength(ladder.getPath().size());
}
return;
}
Iterator<String> i = dictionary.iterator();
while (i.hasNext()) {
String string = i.next();
if(differByOne(string, ladder.getLastWord()) && !ladder.getPath().contains(string)){
List<String> path = ladder.getPath();
path.add(string);
//We found the new word in intermediate path, Start exploring new word from scratch again.
recursiveHelperShortest(startWord, endWord, dictionary, new Ladder(path, ladder.getLength()+1, string), allPath, shortestPath);
//After exploring new word, remove it from intermediate path.
path.remove(path.size()-1);
}
}
}
private static boolean differByOne(String word1, String word2){
if (word1.length() != word2.length()) {
return false;
}
int diffCount = 0;
for (int i = 0; i < word1.length(); i++) {
if (word1.charAt(i) != word2.charAt(i)) {
diffCount++;
}
}
return (diffCount == 1);
}
}
You may also like to see
Trapping Rain Water between Towers Problem
Stock Buy Sell to Maximize Profit
How ConcurrentHashMap works and ConcurrentHashMap interview questions.
Serialize and Deserialize a Binary Tree
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment