Word Ladder – Set 2 ( Bi-directional BFS )

• Difficulty Level : Expert
• Last Updated : 01 Dec, 2021

Given a dictionary, and two words start and target (both of the 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 the dictionary and the lengths of all the dictionary words are equal.
Examples:

Input: Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}
start = “TOON”
target = “PLEA”
Output:
TOON -> POON –> POIN –> POIE –> PLIE –> PLEE –> PLEA

Approach: This problem can be solved using the standard BFS approach as discussed here but its performance can be improved by using bi-directional BFS.
Bi-directional BFS doesn’t reduce the time complexity of the solution but it definitely optimizes the performance in many cases. This approach can also be used in many other shortest pathfinding problems where we have sufficient information about the source and the target node. The basic idea involved in bi-directional BFS is to start the search from both the ends of the path.
Therefore, two queues and two visited arrays are needed to be maintained to track both the paths. So, whenever a node (say A) is present in the source queue, encounters a node (say B) which is present in the target queue, then we can calculate the answer by adding the distance of A from source and the distance of B from target minus 1 (one node is common). This way we can calculate the answer in half the time as compared to the standard BFS approach. This method is also known as the meet-in-the-middle BFS approach.
Below is the implementation of the above approach:

Python3

Output:
7

Time Complexity: O(N^2), where N is the length of the string.
Auxiliary Space: O(N).

My Personal Notes arrow_drop_up
{"ft_lang_label":"__label__en","ft_lang_prob":0.57790744,"math_prob":0.91170275,"size":13207,"snap":"2022-05-2022-21","text_gpt3_token_len":3931,"char_repetition_ratio":0.1465576,"word_repetition_ratio":0.44692007,"special_character_ratio":0.31877035,"punctuation_ratio":0.18326391,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9685039,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-16T19:10:56Z\",\"WARC-Record-ID\":\"<urn:uuid:ba15a776-3022-4a21-9acf-1d3d3f640ad2>\",\"Content-Length\":\"217196\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8c83c91b-e449-4bd0-a342-ff3fd576422e>\",\"WARC-Concurrent-To\":\"<urn:uuid:59820923-fab5-4a63-8cca-85042c2b98ee>\",\"WARC-IP-Address\":\"23.46.150.51\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/word-ladder-set-2-bi-directional-bfs/?ref=lbp\",\"WARC-Payload-Digest\":\"sha1:FM2DSOOCZVHFWVCOL7SOKTVYGRTFAUKN\",\"WARC-Block-Digest\":\"sha1:XE744AMMUHAJ4D6FCSE3DH4TCH5PDHLR\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320300010.26_warc_CC-MAIN-20220116180715-20220116210715-00193.warc.gz\"}"}