Word Ladder (Length of shortest chain to reach a target word)
Given a dictionary, and two words ‘start’ and ‘target’ (both of same length). Find length of the smallest chain from ‘start’ to ‘target’ if it exists, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the ‘target’ word exists in dictionary and length of all dictionary words is same.
The idea is to use BFS. We start from the given start word, traverse all words that adjacent (differ by one character) to it and keep doing so until we find the target word or we have traversed all words.
Below is C++ implementation of above idea.
// C++ program to find length of the shortest chain
// transformation from source to target
// To check if strings differ by exactly one character
boolisadjacent(string& a, string& b)
intcount = 0; // to store count of differences
intn = a.length();
// Iterate through all characters and return false
// if there are more than one mismatching characters
for(inti = 0; i < n; i++)
if(a[i] != b[i]) count++;
if(count > 1) returnfalse;
returncount == 1 ? true: false;
// A queue item to store word and minimum chain length
// to reach the word.
// Returns length of shortest chain to reach 'target' from 'start'
// using minimum number of adjacent moves. D is dictionary