What is the word ladder problem?

In the word ladder problem, you are given a list of words, a starting_word, and an ending_word.The problem requires you to find the minimum number of transitions required to convert the starting_word into the ending_word. There are a few conditions for this problem:


  • All the words should be of the same length.
  • There are no duplicates in the given list.
  • starting_word and ending_word should be non-empty.
  • starting_word and ending_word should not be the same.
  • A t​ransition can only occur if two words differ by one character/alphabet.

1 of 6

Implementation​

The description of the functions, used in the code, are given below:

  • differby1(): This function returns true if two strings mismatch by one character. It returns false if otherwise.
  • wordLadder(): This function calculates the number of transitions required for the conversion.
#include<bits/stdc++.h>
using namespace std;
bool differby1(string& str1, string& str2);
// the Word_trans object will store the string and
// maintain the length of transitions.
class Word_trans
{
public:
string word;
int len;
};
// this function finds the word ladder.
int wordLadder(string& starting_word, string& ending_word, set<string> &list)
{
// create a queue for BFS and insert 'start' as source vertex
queue<Word_trans> trans;
Word_trans temp = {starting_word, 1}; // Chain length for start word is 1
trans.push(temp);
while (!trans.empty())
{
Word_trans curr = trans.front();
trans.pop();
// traverse all the words of the list
for (set<string>::iterator it = list.begin(); it != list.end(); it++)
{
string str = *it;
if (differby1(curr.word, str))
{
// add the word to trans if diffby1 returns true.
temp.word = str;
temp.len = curr.len + 1;
trans.push(temp);
// remove the word form the list
list.erase(str);
// if the str is equal to ending_word then return the number of transitions.
if (str == ending_word)
return temp.len;
}
}
}
return 0;
}
// function for checking whether two strings
// differ by one character
bool differby1(string& str1, string& str2)
{
int count = 0;
int n = str1.length();
for (int i = 0; i < n; i++)
{
if (str1[i] != str2[i])
count++;
if (count > 1)
return false;
}
if(count == 1)// return true if mismatching count is 1.
return true;
return false;// else return false.
}
// main program
int main()
{
// starting and ending word
string starting_word = "sail";
string ending_word = "ruin";
// making a list
set<string> list;
list.insert("mail");
list.insert("main");
list.insert("rain");
list.insert("ruin");
cout << "The number of transitions required: ";
cout<< wordLadder(starting_word, ending_word, list);
return 0;
}

Free Resources

HowDev By Educative. Copyright ©2025 Educative, Inc. All rights reserved