{"id":415,"date":"2017-09-25T22:05:15","date_gmt":"2017-09-26T05:05:15","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=415"},"modified":"2019-09-29T21:39:40","modified_gmt":"2019-09-30T04:39:40","slug":"127-word-ladder","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/127-word-ladder\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 127. Word Ladder"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 127. Word Ladder - \u5237\u9898\u627e\u5de5\u4f5c EP71\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/vWPCm69MSfs?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><a href=\"https:\/\/leetcode.com\/problems\/word-ladder\/description\/\">https:\/\/leetcode.com\/problems\/word-ladder\/description\/<\/a><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given two words (<i>beginWord<\/i>&nbsp;and&nbsp;<i>endWord<\/i>), and a dictionary&#8217;s word list, find the length of shortest transformation sequence from&nbsp;<i>beginWord<\/i>&nbsp;to&nbsp;<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&nbsp;<i>beginWord<\/i>&nbsp;is&nbsp;<i>not<\/i>&nbsp;a transformed word.<\/li>\n<\/ol>\n<p>For example,<\/p>\n<p>Given:<br \/>\n<i>beginWord<\/i>&nbsp;=&nbsp;<code>\"hit\"<\/code><br \/>\n<i>endWord<\/i>&nbsp;=&nbsp;<code>\"cog\"<\/code><br \/>\n<i>wordList<\/i>&nbsp;=&nbsp;<code>[\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]<\/code><\/p>\n<p>As one shortest transformation is&nbsp;<code>\"hit\" -&gt; \"hot\" -&gt; \"dot\" -&gt; \"dog\" -&gt; \"cog\"<\/code>,<br \/>\nreturn its length&nbsp;<code>5<\/code>.<\/p>\n<p><b>Note:<\/b><\/p>\n<ul>\n<li>Return 0 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&nbsp;<i>beginWord<\/i>&nbsp;and&nbsp;<i>endWord<\/i>&nbsp;are non-empty and are not the same.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p><script async=\"\" src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display:block\" data-ad-format=\"fluid\" data-ad-layout-key=\"-fb+5w+4e-db+86\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"2162692788\"><\/ins><br \/>\n<script><br \/>\n     (adsbygoogle = window.adsbygoogle || []).push({});<br \/>\n<\/script><\/p>\n<p>BFS<\/p>\n<p><span style=\"font-weight: 400;\">Time Complexity: O(n*26^<\/span><span style=\"font-weight: 400;\">l<\/span><span style=\"font-weight: 400;\">) -&gt; O(n*26^<\/span><span style=\"font-weight: 400;\">l\/2<\/span><span style=\"font-weight: 400;\">), l = len(word), n=|wordList|<\/span><\/p>\n<p><span style=\"font-weight: 400;\">Space Complexity: O(n)<\/span><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-423\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-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\/127-ep71-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-422\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-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\/127-ep71-4.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-420\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-4.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-4-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-4-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\/127-ep71-3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-421\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-3-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/127-ep71-3-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/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><br \/>\n     (adsbygoogle = window.adsbygoogle || []).push({});<br \/>\n<\/script><\/p>\n<h1><strong>Solution 1: BFS<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\n\/\/ Running time: 93 ms\nclass Solution {\npublic:\n    int ladderLength(string beginWord, string endWord, vector&lt;string&gt;&amp; wordList) {\n        unordered_set&lt;string&gt; dict(wordList.begin(), wordList.end());        \n        if (!dict.count(endWord)) return 0;\n        \n        queue&lt;string&gt; q;\n        q.push(beginWord);\n        \n        int l = beginWord.length();\n        int step = 0;\n        \n        while (!q.empty()) {\n            ++step;\n            for (int size = q.size(); size &gt; 0; size--) {                \n                string w = q.front();                \n                q.pop();\n                for (int i = 0; i &lt; l; i++) {                \n                    char ch = w[i];\n                    for (int j = 'a'; j &lt;= 'z'; j++) {\n                        w[i] = j;\n                        \/\/ Found the solution\n                        if (w == endWord) return step + 1;\n                        \/\/ Not in dict, skip it\n                        if (!dict.count(w)) continue;\n                        \/\/ Remove new word from dict\n                        dict.erase(w);\n                        \/\/ Add new word into queue\n                        q.push(w);                    \n                    }\n                    w[i] = ch;\n                }\n            }\n        }\n        return 0;\n    }\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\n\/\/ Running time: 92 ms (&lt;76.61%)\nclass Solution {\n  public int ladderLength(String beginWord, String endWord, List&lt;String&gt; wordList) {\n    Set&lt;String&gt; dict = new HashSet&lt;&gt;();\n    for (String word : wordList) dict.add(word);\n    \n    if (!dict.contains(endWord)) return 0;\n    \n    Queue&lt;String&gt; q = new ArrayDeque&lt;&gt;();\n    q.offer(beginWord);\n    \n    int l = beginWord.length();\n    int steps = 0;\n    \n    while (!q.isEmpty()) {\n      ++steps;\n      for (int s = q.size(); s &gt; 0; --s) {\n        String w = q.poll();        \n        char[] chs = w.toCharArray();\n        for (int i = 0; i &lt; l; ++i) {\n          char ch = chs[i];\n          for (char c = 'a'; c &lt;= 'z'; ++c) {\n            if (c == ch) continue;\n            chs[i] = c;\n            String t = new String(chs);         \n            if (t.equals(endWord)) return steps + 1;            \n            if (!dict.contains(t)) continue;            \n            dict.remove(t);            \n            q.offer(t);\n          }\n          chs[i] = ch;\n        }\n      }\n    }\n    return 0;\n  }\n}<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2:&nbsp;Bidirectional BFS<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Running time: 32 ms (better than 96.6%)\nclass Solution {\npublic:\n    int ladderLength(string beginWord, string endWord, vector&lt;string&gt;&amp; wordList) {\n        unordered_set&lt;string&gt; dict(wordList.begin(), wordList.end());        \n        if (!dict.count(endWord)) return 0;\n        \n        int l = beginWord.length();\n        \n        unordered_set&lt;string&gt; q1{beginWord};\n        unordered_set&lt;string&gt; q2{endWord};\n                \n        int step = 0;\n        \n        while (!q1.empty() &amp;&amp; !q2.empty()) {\n            ++step;\n            \n            \/\/ Always expend the smaller queue first\n            if (q1.size() &gt; q2.size())\n                std::swap(q1, q2);\n                        \n            unordered_set&lt;string&gt; q;\n            \n            for (string w : q1) {\n                for (int i = 0; i &lt; l; i++) {\n                    char ch = w[i];\n                    for (int j = 'a'; j &lt;= 'z'; j++) {\n                        w[i] = j;\n                        if (q2.count(w)) return step + 1;\n                        if (!dict.count(w)) continue;                        \n                        dict.erase(w);\n                        q.insert(w);\n                    }\n                    w[i] = ch;\n                }\n            }\n            \n            std::swap(q, q1);\n        }\n        \n        return 0;\n    }\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\n\/\/ Running time: 31 ms (&lt;95.17%)\nclass Solution {\n  public int ladderLength(String beginWord, String endWord, List&lt;String&gt; wordList) {\n    Set&lt;String&gt; dict = new HashSet&lt;&gt;();\n    for (String word : wordList) dict.add(word);\n    \n    if (!dict.contains(endWord)) return 0;\n    \n    Set&lt;String&gt; q1 = new HashSet&lt;&gt;();\n    Set&lt;String&gt; q2 = new HashSet&lt;&gt;();\n    q1.add(beginWord);\n    q2.add(endWord);\n    \n    int l = beginWord.length();\n    int steps = 0;\n    \n    while (!q1.isEmpty() &amp;&amp; !q2.isEmpty()) {\n      ++steps;\n      \n      if (q1.size() &gt; q2.size()) {\n        Set&lt;String&gt; tmp = q1;\n        q1 = q2;\n        q2 = tmp;\n      }\n      \n      Set&lt;String&gt; q = new HashSet&lt;&gt;();\n      \n      for (String w : q1) {        \n        char[] chs = w.toCharArray();\n        for (int i = 0; i &lt; l; ++i) {\n          char ch = chs[i];\n          for (char c = 'a'; c &lt;= 'z'; ++c) {\n            chs[i] = c;\n            String t = new String(chs);         \n            if (q2.contains(t)) return steps + 1;            \n            if (!dict.contains(t)) continue;            \n            dict.remove(t);        \n            q.add(t);\n          }\n          chs[i] = ch;\n        }\n      }\n      \n      q1 = q;\n    }\n    return 0;\n  }\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \">\"\"\"\nAuthor: Huahua\nRunning time: 115 ms (better than 96.84%)\n\"\"\"\nclass Solution(object):\n    def ladderLength(self, beginWord, endWord, wordList):\n        wordDict = set(wordList)\n        if endWord not in wordDict: return 0\n        \n        l = len(beginWord)\n        s1 = {beginWord}\n        s2 = {endWord}\n        wordDict.remove(endWord)\n        step = 0\n        while len(s1) &gt; 0 and len(s2) &gt; 0:\n            step += 1\n            if len(s1) &gt; len(s2): s1, s2 = s2, s1\n            s = set()   \n            for w in s1:\n                new_words = [\n                    w[:i] + t + w[i+1:]  for t in string.ascii_lowercase for i in xrange(l)]\n                for new_word in new_words:\n                    if new_word in s2: return step + 1\n                    if new_word not in wordDict: continue\n                    wordDict.remove(new_word)                        \n                    s.add(new_word)\n            s1 = s\n        \n        return 0\n<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-126-word-ladder-ii\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 126. Word Ladder II<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-79-word-search\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 79. Word Search<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-139-word-break\/\">[\u89e3\u9898\u62a5\u544a] Leetcode 139. Word Break \u82b1\u82b1\u9171<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-140-word-break-ii\/\">\u82b1\u82b1\u9171 Leetcode 140. Word Break II<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/word-ladder\/description\/ Problem: Given two words (beginWord&nbsp;and&nbsp;endWord), and a dictionary&#8217;s word list, find the length of shortest transformation sequence from&nbsp;beginWord&nbsp;to&nbsp;endWord, such that: Only one letter can&#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,177,87,4,109],"class_list":["post-415","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-medium","tag-shortest-path","tag-string","tag-word","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/415","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=415"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/415\/revisions"}],"predecessor-version":[{"id":5635,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/415\/revisions\/5635"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=415"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=415"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=415"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}