BFS vs DFS with Example in Java

BFS vs DFS with Example

---

Breadth First Search(BFS) Vs Depth First Search(DFS) with example in Java. DFS uses Stack while BFS uses Queue.

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.

There can be many paths for reaching from startWord to endWord, but we have to find shortest path possible.

Read more

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

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.

There can be many paths for reaching from startWord to endWord, but we have to find shortest path possible.

Read more