{"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 &#8211; Word Ladder Length of shortest chain to reach a target word"},"content":{"rendered":"<p>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 id=\"more-135292\"><\/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<p><strong>Example:<\/strong><\/p>\n<pre>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<p>The idea is to use <a href=\"http:\/\/www.geeksforgeeks.org\/breadth-first-traversal-for-a-graph\/\" target=\"_blank\" rel=\"noopener\">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=&#8221;banner&#8221;]\n<p>Below is C++ implementation of above idea.<\/p>\n[pastacode lang=&#8221;cpp&#8221; manual=&#8221;%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&#8217;target&#8217;%20from%20&#8217;start&#8217;%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&#8217;start&#8217;%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&#8221; message=&#8221;C++ Program&#8221; highlight=&#8221;&#8221; provider=&#8221;manual&#8221;\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Length of shortest chain is: 7<\/pre>\n<p>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=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>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}]}}