Print all possible shortest chains to reach a target word | C ++ Program to implement the above approach ; Function to print all possible shortest sequences starting from start to target . ; Find words differing by a single character with word ; Find next word in dict by changing each element from ' a ' to ' z ' ; Function to get all the shortest possible sequences starting from ' start ' to ' target ' ; Store all the shortest path . ; Store visited words in list ; Queue used to find the shortest path ; Stores the distinct words from given list ; Stores whether the shortest path is found or not ; Explore the next level ; Find words differing by a single character ; Add words to the path . ; Found the target ; If already reached target ; Erase all visited words . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void displaypath ( vector < vector < string > > & res ) { for ( int i = 0 ; i < res . size ( ) ; i ++ ) { cout << " [ ▁ " ; for ( int j = 0 ; j < res [ 0 ] . size ( ) ; j ++ ) { cout << res [ i ] [ j ] << " , ▁ " ; } cout << " ▁ ] STRNEWLINE " ; } } vector < string > addWord ( string word , unordered_set < string > & dict ) { vector < string > res ; for ( int i = 0 ; i < word . size ( ) ; i ++ ) { char s = word [ i ] ; for ( char c = ' a ' ; c <= ' z ' ; c ++ ) { word [ i ] = c ; if ( dict . count ( word ) ) res . push_back ( word ) ; } word [ i ] = s ; } return res ; } vector < vector < string > > findLadders ( vector < string > & Dict , string beginWord , string endWord ) { vector < vector < string > > res ; unordered_set < string > visit ; queue < vector < string > > q ; unordered_set < string > dict ( Dict . begin ( ) , Dict . end ( ) ) ; q . push ( { beginWord } ) ; bool flag = false ; while ( ! q . empty ( ) ) { int size = q . size ( ) ; for ( int i = 0 ; i < size ; i ++ ) { vector < string > cur = q . front ( ) ; q . pop ( ) ; vector < string > newadd ; newadd = addWord ( cur . back ( ) , dict ) ; for ( int j = 0 ; j < newadd . size ( ) ; j ++ ) { vector < string > newline ( cur . begin ( ) , cur . end ( ) ) ; newline . push_back ( newadd [ j ] ) ; if ( newadd [ j ] == endWord ) { flag = true ; res . push_back ( newline ) ; } visit . insert ( newadd [ j ] ) ; q . push ( newline ) ; } } if ( flag ) { break ; } for ( auto it : visit ) { dict . erase ( it ) ; } visit . clear ( ) ; } return res ; } int main ( ) { vector < string > str { " ted " , " tex " , " red " , " tax " , " tad " , " den " , " rex " , " pee " } ; string beginWord = " red " ; string endWord = " tax " ; vector < vector < string > > res = findLadders ( str , beginWord , endWord ) ; displaypath ( res ) ; }