Print all possible shortest chains to reach a target word | Python 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
from collections import deque NEW_LINE from typing import Deque , List , Set NEW_LINE def displaypath ( res : List [ List [ str ] ] ) : NEW_LINE INDENT for i in res : NEW_LINE INDENT print ( " [ ▁ " , end = " " ) for j in i : print ( j , end = " , ▁ " ) print ( " ] " ) NEW_LINE DEDENT DEDENT def addWord ( word : str , Dict : Set ) : NEW_LINE INDENT res : List [ str ] = [ ] NEW_LINE wrd = list ( word ) NEW_LINE DEDENT ' NEW_LINE INDENT for i in range ( len ( wrd ) ) : NEW_LINE INDENT s = wrd [ i ] NEW_LINE c = ' a ' NEW_LINE while c <= ' z ' : NEW_LINE INDENT wrd [ i ] = c NEW_LINE if ' ' . join ( wrd ) in Dict : NEW_LINE INDENT res . append ( ' ' . join ( wrd ) ) NEW_LINE DEDENT c = chr ( ord ( c ) + 1 ) NEW_LINE DEDENT wrd [ i ] = s NEW_LINE DEDENT return res NEW_LINE DEDENT ' NEW_LINE def findLadders ( Dictt : List [ str ] , beginWord : str , endWord : str ) : NEW_LINE INDENT res : List [ List [ str ] ] = [ ] NEW_LINE visit = set ( ) NEW_LINE q : Deque [ List [ str ] ] = deque ( ) NEW_LINE Dict = set ( ) NEW_LINE for i in Dictt : NEW_LINE INDENT Dict . add ( i ) NEW_LINE DEDENT q . append ( [ beginWord ] ) NEW_LINE flag = False NEW_LINE while q : NEW_LINE INDENT size = len ( q ) NEW_LINE for i in range ( size ) : NEW_LINE INDENT cur = q [ 0 ] NEW_LINE q . popleft ( ) NEW_LINE newadd = [ ] NEW_LINE newadd = addWord ( cur [ - 1 ] , Dict ) NEW_LINE for j in range ( len ( newadd ) ) : NEW_LINE INDENT newline = cur . copy ( ) NEW_LINE newline . append ( newadd [ j ] ) NEW_LINE if ( newadd [ j ] == endWord ) : NEW_LINE INDENT flag = True NEW_LINE res . append ( newline ) NEW_LINE DEDENT visit . add ( newadd [ j ] ) NEW_LINE q . append ( newline ) NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT break NEW_LINE DEDENT for it in visit : NEW_LINE INDENT Dict . remove ( it ) NEW_LINE DEDENT visit . clear ( ) NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = [ " ted " , " tex " , " red " , " tax " , " tad " , " den " , " rex " , " pee " ] NEW_LINE beginWord = " red " NEW_LINE endWord = " tax " NEW_LINE res = findLadders ( string , beginWord , endWord ) NEW_LINE displaypath ( res ) NEW_LINE DEDENT