What do you mean by BFS?

Breadth-First Search (BFS) is a vertex-based method for finding the shortest path in a graph. It uses a Queue data structure that follows the first-in, first-out principle. In BFS, one vertex is visited and marked at a time, and then its neighbours are visited and stored in the queue. This is done until the queue becomes empty or you get your result.

How do you solve a word ladder?

In a word ladder puzzle, you must replace one letter at a time to make the change happen gradually. Each stage requires you to change one word into another; You cannot change a word into a non-word. Generally, BFS is used to solve these types of puzzles.

Word Ladder - Naukri Code 360

Question:

Given a dictionary and the two words 'start' and 'target' (both of the same length). The task is to find the length of the shortest chain from 'start' to 'target' where adjacent words in the chain differ by one character, and each word in the chain is a valid word (i.e., it exists in the dictionary).

Assume that the 'target' word is in the dictionary and that all dictionary words are the same length.

Input:

Dictionary: A set of strings of length n.

A ‘start’ string.

A ‘target’ string.

Output:

An integer: Length of the shortest chain from ‘start’ to ‘target.’

The questions you can ask the interviewer:

What can be the range of the length of the chain?
What is the range of the length of the words in the dictionary?

Examples:

Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Input: Dictionary = {poon, plee, same, poie, pool, plie, poin}

start = tool

target = poin

Output: 4

Explanation: The smallest chain: tool - pool - poon - poin.

‘t’ in the tool is replaced by ‘p’ to make the word pool.

‘l’ in the pool is replaced by ‘n’ to make the word poon.

‘o’ in the poon is replaced by ‘i’ to make the word poin.

Input: Dictionary = {aaaa, aaab, saaa, aabb, abbb, abcd, saab, abcd}

start = caaa

target = poin

Output: 6

Explanation: The smallest chain: caaa - aaa - aaab - aabb - abbb - abcb.

Recommended: Please try to solve it yourself before moving on to the solution.

Solution:

Idea: The idea is to use BFS. Start from the given word and use BFS to reach the target.

Challenge: How to avoid infinite loop or repetition of words?

Solution: Remove the word from the dictionary once it is included in the chain or maintain a set to avoid repetition

Algorithm:

Declare a queue and add the start word in it.
Initiate a variable length to count the length of the smallest chain.
Run a loop until the queue becomes empty or we find our target.
Traverse all the adjacent words( words that differ by only one character ) to the word on the top of the queue and push them to the queue for BFS.
Increase the length after traversing all the adjacent words.
Keep doing it until we find our target word.
Return the length.

C++

#include <bits/stdc++.h>
using namespace std;

int shortestLen(set<string>& Dict, string start, string target)
{
  // If the start is the same as the target, the chain length will be 0.
if(start == target)
return 0;

   // initially length will be 1, including the word 'start'.
int level = 1;
int n = start.size();

  // initialise the queue and push start to it.
queue<string> q;
q.push(start);

while (!q.empty()) {

  // increase the level of the chain.
level++;
int size = q.size();

  // Traverse all the adjacent words.
for (int i = 0; i < size; i++) {
string word = q.front();
q.pop();

// Iterate over every character of the word.
for (int pos = 0; pos < n; pos++) {
char c = word[pos];

// Replace the current character with every possible alphabet
for (char k = 'a'; k <= 'z'; k++) {
word[pos] = k;

// If this word is equal to the target word, return the length.
if (word == target)
return level;

//if the word is not in the dictionary, continue.
if (Dict.find(word) == Dict.end())
continue;

// push the word into the queue and remove it from the dictionary to avoid repetition.
q.push(word);
Dict.erase(word);
}

// Restore the original character.
word[pos] = c;
}
}
}
return 0;
}

int main()
{
set<string> Dict;
Dict.insert("poon");
Dict.insert("plee");
Dict.insert("same");
Dict.insert("poie");
Dict.insert("plie");
Dict.insert("pool");
Dict.insert("plie");
Dict.insert("poin");
string start = "tool";
string target = "poin";
cout << "The length of the shortest chain is: "
<< shortestLen(Dict, start, target);
return 0;
}

Output:

Time Complexity: O(n²m), where n is the length of the string and m is the number of items in the dictionary.

Space Complexity: O(m*n). As a total of m strings of length n are stored in the queue.

FAQs

What do you mean by BFS?
Breadth-First Search (BFS) is a vertex-based method for finding the shortest path in a graph. It uses a Queue data structure that follows the first-in, first-out principle. In BFS, one vertex is visited and marked at a time, and then its neighbours are visited and stored in the queue. This is done until the queue becomes empty or you get your result.
How do you solve a word ladder?
In a word ladder puzzle, you must replace one letter at a time to make the change happen gradually. Each stage requires you to change one word into another; You cannot change a word into a non-word. Generally, BFS is used to solve these types of puzzles.

Key Takeaways

In this article, we solved a famous word ladder problem in which we were given a dictionary and the two words 'start' and 'target' (both of the same length). The task was to find the length of the shortest chain from 'start' to 'target' where adjacent words in the chain differ by only one character, and each word in the chain is a valid word (i.e., it exists in the dictionary).

We used the BFS algorithm to solve the problem. Starting from the ‘start’ word, we applied BFS on all the adjacent words of the ‘start’ and pushed them to queue. And repeated this process until we got our ‘target’ word.

The problem was solved in O(n²m) time.

Challenge: Can you solve this puzzle?

Click here to learn more about BFS and DFS.

Also check out - Data Dictionary In Software Engineering

Apart from that, you can use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.