{"id":427,"date":"2017-09-26T21:27:00","date_gmt":"2017-09-27T04:27:00","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=427"},"modified":"2018-08-19T18:38:25","modified_gmt":"2018-08-20T01:38:25","slug":"leetcode-126-word-ladder-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-126-word-ladder-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 126. Word Ladder II"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 126. Word Ladder II - \u5237\u9898\u627e\u5de5\u4f5c EP72\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/PblfQrdWXQ4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given two words (<i>beginWord<\/i>\u00a0and\u00a0<i>endWord<\/i>), and a dictionary&#8217;s word list, find all shortest transformation sequence(s) from\u00a0<i>beginWord<\/i>\u00a0to\u00a0<i>endWord<\/i>, such that:<\/p>\n<ol>\n<li>Only one letter can be changed at a time<\/li>\n<li>Each transformed word must exist in the word list. Note that\u00a0<i>beginWord<\/i>\u00a0is\u00a0<i>not<\/i>\u00a0a transformed word.<\/li>\n<\/ol>\n<p>For example,<\/p>\n<p>Given:<br \/>\n<i>beginWord<\/i>\u00a0=\u00a0<code>\"hit\"<\/code><br \/>\n<i>endWord<\/i>\u00a0=\u00a0<code>\"cog\"<\/code><br \/>\n<i>wordList<\/i>\u00a0=\u00a0<code>[\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]<\/code><\/p>\n<p>Return<\/p>\n<pre>  [\r\n    [\"hit\",\"hot\",\"dot\",\"dog\",\"cog\"],\r\n    [\"hit\",\"hot\",\"lot\",\"log\",\"cog\"]\r\n  ]\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ul>\n<li>Return an empty list if there is no such transformation sequence.<\/li>\n<li>All words have the same length.<\/li>\n<li>All words contain only lowercase alphabetic characters.<\/li>\n<li>You may assume no duplicates in the word list.<\/li>\n<li>You may assume\u00a0<i>beginWord<\/i>\u00a0and\u00a0<i>endWord<\/i>\u00a0are non-empty and are not the same.<\/li>\n<\/ul>\n<p><strong>Idea:<\/strong><\/p>\n<p>BFS to construct the graph + DFS to extract the paths<\/p>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-433\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-432\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-431\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-3-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/126-ep72-3-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Solutions:<\/strong><\/p>\n<p>C++, BFS 1<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running Time: 216 ms (better than 65.42%)\r\nclass Solution {\r\npublic:\r\n    vector&lt;vector&lt;string&gt;&gt; findLadders(string beginWord, string endWord, vector&lt;string&gt;&amp; wordList) {\r\n        \r\n        unordered_set&lt;string&gt; dict(wordList.begin(), wordList.end());        \r\n        if (!dict.count(endWord)) return {};\r\n        dict.erase(beginWord);\r\n        dict.erase(endWord);\r\n        \r\n        unordered_map&lt;string, int&gt; steps{{beginWord, 1}};\r\n        unordered_map&lt;string, vector&lt;string&gt;&gt; parents;\r\n        queue&lt;string&gt; q;\r\n        q.push(beginWord);\r\n        \r\n        vector&lt;vector&lt;string&gt;&gt; ans;\r\n        \r\n        const int l = beginWord.length();\r\n        int step = 0;        \r\n        bool found = false;\r\n        \r\n        while (!q.empty() &amp;&amp; !found) {\r\n            ++step;            \r\n            for (int size = q.size(); size &gt; 0; size--) {\r\n                const string p = q.front(); q.pop();\r\n                string w = p;\r\n                for (int i = 0; i &lt; l; i++) {\r\n                    const char ch = w[i];\r\n                    for (int j = 'a'; j &lt;= 'z'; j++) {\r\n                        if (j == ch) continue;\r\n                        w[i] = j;\r\n                        if (w == endWord) {\r\n                            parents[w].push_back(p);\r\n                            found = true;\r\n                        } else {\r\n                            \/\/ Not a new word, but another transform\r\n                            \/\/ with the same number of steps\r\n                            if (steps.count(w) &amp;&amp; step &lt; steps.at(w))\r\n                                parents[w].push_back(p);\r\n                        }\r\n                        \r\n                        if (!dict.count(w)) continue;\r\n                        dict.erase(w);\r\n                        q.push(w);\r\n                        steps[w] = steps.at(p) + 1;\r\n                        parents[w].push_back(p);\r\n                    }\r\n                    w[i] = ch;\r\n                }\r\n            }\r\n        }\r\n        \r\n        if (found) {\r\n            vector&lt;string&gt; curr{endWord};\r\n            getPaths(endWord, beginWord, parents, curr, ans);\r\n        }\r\n    \r\n        return ans;\r\n    }\r\nprivate:\r\n    void getPaths(const string&amp; word, \r\n                  const string&amp; beginWord, \r\n                  const unordered_map&lt;string, vector&lt;string&gt;&gt;&amp; parents,\r\n                  vector&lt;string&gt;&amp; curr,\r\n                  vector&lt;vector&lt;string&gt;&gt;&amp; ans) {        \r\n        \r\n        if (word == beginWord) {\r\n            ans.push_back(vector&lt;string&gt;(curr.rbegin(), curr.rend()));\r\n            return;\r\n        }\r\n        \r\n        for (const string&amp; p : parents.at(word)) {\r\n            curr.push_back(p);\r\n            getPaths(p, beginWord, parents, curr, ans);\r\n            curr.pop_back();\r\n        }        \r\n    }\r\n};<\/pre>\n<p><ins class=\"adsbygoogle\"\n     style=\"display:block; text-align:center;\"\n     data-ad-layout=\"in-article\"\n     data-ad-format=\"fluid\"\n     data-ad-client=\"ca-pub-2404451723245401\"\n     data-ad-slot=\"7983117522\"><br \/>\n<\/ins><\/p>\n<p>C++ \/ BFS 2<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 129 ms (better than 80.67%)\r\nclass Solution {\r\npublic:\r\n    vector&lt;vector&lt;string&gt;&gt; findLadders(string beginWord, string endWord, vector&lt;string&gt;&amp; wordList) {\r\n        vector&lt;vector&lt;string&gt;&gt; ans;\r\n        unordered_set&lt;string&gt; dict(wordList.begin(), wordList.end());\r\n        if (!dict.count(endWord)) return ans;\r\n        dict.erase(endWord);        \r\n        \r\n        const int l = beginWord.length();\r\n        unordered_set&lt;string&gt; q{beginWord}, p;\r\n        unordered_map&lt;string, vector&lt;string&gt;&gt; children;\r\n        bool found = false;\r\n        \r\n        while (!q.empty() &amp;&amp; !found) {\r\n            \r\n            for (const string&amp; word : q) \r\n                dict.erase(word);\r\n            \r\n            for (const string&amp; word : q) {                                \r\n                string curr = word;\r\n                for (int i = 0; i &lt; l; i++) {\r\n                    char ch = curr[i];\r\n                    for (int j = 'a'; j &lt;= 'z'; j++) {\r\n                        curr[i] = j;\r\n                        if (curr == endWord) {\r\n                            found = true;\r\n                            children[word].push_back(curr);\r\n                        } else if (dict.count(curr) &amp;&amp; !found) {\r\n                            p.insert(curr);\r\n                            children[word].push_back(curr);\r\n                        }\r\n                    }\r\n                    curr[i] = ch;\r\n                }\r\n            }\r\n            \r\n            std::swap(p, q);\r\n            p.clear();\r\n        }\r\n        \r\n        if (found) {\r\n            vector&lt;string&gt; path{beginWord};\r\n            getPaths(beginWord, endWord, children, path, ans);\r\n        }\r\n        \r\n        return ans;\r\n    }\r\nprivate:\r\n    void getPaths(const string&amp; word, \r\n                  const string&amp; endWord,                   \r\n                  const unordered_map&lt;string, vector&lt;string&gt;&gt;&amp; children,\r\n                  vector&lt;string&gt;&amp; path, \r\n                  vector&lt;vector&lt;string&gt;&gt;&amp; ans) {\r\n        if (word == endWord) {\r\n            ans.push_back(path);\r\n            return;\r\n        }\r\n        \r\n        const auto it = children.find(word);\r\n        if (it == children.cend()) return;\r\n        \r\n        for (const string&amp; child : it-&gt;second) {\r\n            path.push_back(child);\r\n            getPaths(child, endWord, children, path, ans);\r\n            path.pop_back();\r\n        }\r\n    }    \r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ \/ Bidirectional BFS<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 39 ms (better than 93.74%)\r\nclass Solution {\r\npublic:\r\n    vector&lt;vector&lt;string&gt;&gt; findLadders(string beginWord, string endWord, vector&lt;string&gt;&amp; wordList) {\r\n        vector&lt;vector&lt;string&gt;&gt; ans;\r\n        unordered_set&lt;string&gt; dict(wordList.begin(), wordList.end());\r\n        if (!dict.count(endWord)) return ans;\r\n        \r\n        int l = beginWord.length();\r\n        \r\n        unordered_set&lt;string&gt; q1{beginWord};\r\n        unordered_set&lt;string&gt; q2{endWord};\r\n        unordered_map&lt;string, vector&lt;string&gt;&gt; children;\r\n\r\n        bool found = false;\r\n        bool backward = false;\r\n        \r\n        while (!q1.empty() &amp;&amp; !q2.empty() &amp;&amp; !found) {            \r\n            \/\/ Always expend the smaller queue first\r\n            if (q1.size() &gt; q2.size()) {\r\n                std::swap(q1, q2);\r\n                backward = !backward;\r\n            }\r\n            \r\n            for (const string&amp; w : q1)\r\n                dict.erase(w);\r\n            for (const string&amp; w : q2)\r\n                dict.erase(w);\r\n                        \r\n            unordered_set&lt;string&gt; q;\r\n            \r\n            for (const string&amp; word : q1) {\r\n                string curr = word;\r\n                for (int i = 0; i &lt; l; i++) {\r\n                    char ch = curr[i];\r\n                    for (int j = 'a'; j &lt;= 'z'; j++) {\r\n                        curr[i] = j;\r\n                        \r\n                        const string* parent = &amp;word;\r\n                        const string* child = &amp;curr;\r\n                        \r\n                        if (backward)\r\n                            std::swap(parent, child);\r\n                        \r\n                        if (q2.count(curr)) {\r\n                            found = true;\r\n                            children[*parent].push_back(*child);\r\n                        } else if (dict.count(curr) &amp;&amp; !found) {\r\n                            q.insert(curr);\r\n                            children[*parent].push_back(*child);\r\n                        }\r\n                    }\r\n                    curr[i] = ch;\r\n                }\r\n            }\r\n            \r\n            std::swap(q, q1);\r\n        }\r\n        \r\n        if (found) {\r\n            vector&lt;string&gt; path{beginWord};\r\n            getPaths(beginWord, endWord, children, path, ans);\r\n        }\r\n        \r\n        return ans;\r\n    }\r\nprivate:\r\n    void getPaths(const string&amp; word, \r\n                  const string&amp; endWord,                   \r\n                  const unordered_map&lt;string, vector&lt;string&gt;&gt;&amp; children, \r\n                  vector&lt;string&gt;&amp; path, \r\n                  vector&lt;vector&lt;string&gt;&gt;&amp; ans) {        \r\n        if (word == endWord) {\r\n            ans.push_back(path);\r\n            return;\r\n        }\r\n        \r\n        const auto it = children.find(word);\r\n        if (it == children.cend()) return;\r\n        \r\n        for (const string&amp; child : it-&gt;second) {\r\n            path.push_back(child);\r\n            getPaths(child, endWord, children, path, ans);\r\n            path.pop_back();\r\n        }\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given two words (beginWord\u00a0and\u00a0endWord), and a dictionary&#8217;s word list, find all shortest transformation sequence(s) from\u00a0beginWord\u00a0to\u00a0endWord, such that: Only one letter can be changed at&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[34,110,33,77,217],"class_list":["post-427","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-bidirectional-bfs","tag-dfs","tag-graph","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/427","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=427"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/427\/revisions"}],"predecessor-version":[{"id":3626,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/427\/revisions\/3626"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=427"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=427"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=427"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}