{"id":26611,"date":"2017-12-21T20:37:57","date_gmt":"2017-12-21T15:07:57","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26611"},"modified":"2017-12-21T20:37:57","modified_gmt":"2017-12-21T15:07:57","slug":"c-programming-word-ladder-length-shortest-chain-reach-target-word","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-word-ladder-length-shortest-chain-reach-target-word\/","title":{"rendered":"C++ Programming – Word Ladder Length of shortest chain to reach a target word"},"content":{"rendered":"

Given a dictionary, and two words \u2018start\u2019 and \u2018target\u2019 (both of same length). Find length of the smallest chain from \u2018start\u2019 to \u2018target\u2019 if it exists, such that adjacent words in the chain only differ by one character and <\/span>each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the \u2018target\u2019 word exists in dictionary and length of all dictionary words is same.<\/p>\n

Example:<\/strong><\/p>\n

Input:  Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}\r\n             start = TOON\r\n             target = PLEA\r\nOutput: 7\r\nExplanation: TOON - POON - POIN - POIE - PLIE - PLEE - PLEA<\/pre>\n
The idea is to use BFS<\/a>. 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.<\/p>\n[ad type=\u201dbanner\u201d]\n
Below is C++ implementation of above idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20length%20of%20the%20shortest%20chain%0A%2F%2F%20transformation%20from%20source%20to%20target%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20To%20check%20if%20strings%20differ%20by%20exactly%20one%20character%0Abool%20isadjacent(string%26%20a%2C%20string%26%20b)%0A%7B%0A%20%20%20%20int%20count%20%3D%200%3B%20%20%2F%2F%20to%20store%20count%20of%20differences%0A%20%20%20%20int%20n%20%3D%20a.length()%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20all%20characters%20and%20return%20false%0A%20%20%20%20%2F%2F%20if%20there%20are%20more%20than%20one%20mismatching%20characters%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(a%5Bi%5D%20!%3D%20b%5Bi%5D)%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20if%20(count%20%3E%201)%20return%20false%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20count%20%3D%3D%201%20%3F%20true%20%3A%20false%3B%0A%7D%0A%20%0A%2F%2F%20A%20queue%20item%20to%20store%20word%20and%20minimum%20chain%20length%0A%2F%2F%20to%20reach%20the%20word.%0Astruct%20QItem%0A%7B%0A%20%20%20%20string%20word%3B%0A%20%20%20%20int%20len%3B%0A%7D%3B%0A%20%0A%2F%2F%20Returns%20length%20of%20shortest%20chain%20to%20reach%20\u2019target\u2019%20from%20\u2019start\u2019%0A%2F%2F%20using%20minimum%20number%20of%20adjacent%20moves.%20%20D%20is%20dictionary%0Aint%20shortestChainLen(string%26%20start%2C%20string%26%20target%2C%20set%3Cstring%3E%20%26D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20queue%20for%20BFS%20and%20insert%20\u2019start\u2019%20as%20source%20vertex%0A%20%20%20%20queue%3CQItem%3E%20Q%3B%0A%20%20%20%20QItem%20item%20%3D%20%7Bstart%2C%201%7D%3B%20%20%2F%2F%20Chain%20length%20for%20start%20word%20is%201%0A%20%20%20%20Q.push(item)%3B%0A%20%0A%20%20%20%20%2F%2F%20While%20queue%20is%20not%20empty%0A%20%20%20%20while%20(!Q.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Take%20the%20front%20word%0A%20%20%20%20%20%20%20%20QItem%20curr%20%3D%20Q.front()%3B%0A%20%20%20%20%20%20%20%20Q.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Go%20through%20all%20words%20of%20dictionary%0A%20%20%20%20%20%20%20%20for%20(set%3Cstring%3E%3A%3Aiterator%20it%20%3D%20D.begin()%3B%20it%20!%3D%20D.end()%3B%20it%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Process%20a%20dictionary%20word%20if%20it%20is%20adjacent%20to%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20word%20(or%20vertex)%20of%20BFS%0A%20%20%20%20%20%20%20%20%20%20%20%20string%20temp%20%3D%20*it%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(isadjacent(curr.word%2C%20temp))%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Add%20the%20dictionary%20word%20to%20Q%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20item.word%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20item.len%20%3D%20curr.len%20%2B%201%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Q.push(item)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Remove%20from%20dictionary%20so%20that%20this%20word%20is%20not%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20processed%20again.%20%20This%20is%20like%20marking%20visited%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20D.erase(temp)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20we%20reached%20target%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(temp%20%3D%3D%20target)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20item.len%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%200%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20make%20dictionary%0A%20%20%20%20set%3Cstring%3E%20D%3B%0A%20%20%20%20D.insert(%22poon%22)%3B%0A%20%20%20%20D.insert(%22plee%22)%3B%0A%20%20%20%20D.insert(%22same%22)%3B%0A%20%20%20%20D.insert(%22poie%22)%3B%0A%20%20%20%20D.insert(%22plie%22)%3B%0A%20%20%20%20D.insert(%22poin%22)%3B%0A%20%20%20%20D.insert(%22plea%22)%3B%0A%20%20%20%20string%20start%20%3D%20%22toon%22%3B%0A%20%20%20%20string%20target%20%3D%20%22plea%22%3B%0A%20%20%20%20cout%20%3C%3C%20%22Length%20of%20shortest%20chain%20is%3A%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20shortestChainLen(start%2C%20target%2C%20D)%3B%20%0A%20%20%20%20return%200%3B%20%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
Length of shortest chain is: 7<\/pre>\n
Time Complexity of the above code is O(n\u00b2m) where n is the number of entries originally in the dictionary and m is the size of the string<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Given a dictionary, and two words \u2018start\u2019 and \u2018target\u2019 (both of same length). Find length of the smallest chain from \u2018start\u2019 to \u2018target\u2019 if it exists.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1,73906],"tags":[79315,79288,79310,79316,79314,79304,79307,79312,79295,79294,79292,79309,79284,79298,79283,79289,79311,79286,79291,79297,79299,79282,79302,79303,79301,79305,79293,79285,79296,79287,79313,79308,79290,79300,79306],"class_list":["post-26611","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-graph-algorithms","tag-another-word-for-ladder","tag-answers-to-word-ladders","tag-easy-word-ladders","tag-how-to-make-a-word-ladder","tag-if-else-ladder-in-java","tag-ladder-2","tag-ladder-code","tag-ladder-dictionary","tag-ladder-problem","tag-ladder-questions","tag-ladder-words","tag-question-ladder","tag-transforma-ladder","tag-what-is-a-word-ladder","tag-word-ladder","tag-word-ladder-2","tag-word-ladder-algorithm","tag-word-ladder-answer-key","tag-word-ladder-answers","tag-word-ladder-answers-free","tag-word-ladder-examples","tag-word-ladder-game","tag-word-ladder-ii","tag-word-ladder-java","tag-word-ladder-leetcode","tag-word-ladder-problem","tag-word-ladder-puzzles","tag-word-ladder-solution","tag-word-ladder-solver","tag-word-ladder-solver-free","tag-word-ladder-with-answers","tag-word-ladders-online","tag-word-ladders-pdf","tag-wordladder","tag-world-ladder"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26611","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26611"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26611\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}