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:
starting_word
and ending_word
should be non-empty.starting_word
and ending_word
should not be the same.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 vertexqueue<Word_trans> trans;Word_trans temp = {starting_word, 1}; // Chain length for start word is 1trans.push(temp);while (!trans.empty()){Word_trans curr = trans.front();trans.pop();// traverse all the words of the listfor (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 listlist.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 characterbool 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 programint main(){// starting and ending wordstring starting_word = "sail";string ending_word = "ruin";// making a listset<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