{"id":1324,"date":"2017-12-25T09:13:30","date_gmt":"2017-12-25T17:13:30","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1324"},"modified":"2018-01-01T10:46:14","modified_gmt":"2018-01-01T18:46:14","slug":"leetcode-752-open-the-lock","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-752-open-the-lock\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 752. Open the Lock"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 752. Open the Lock - \u5237\u9898\u627e\u5de5\u4f5c EP141\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/M7GgV6TJTdc?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<div class=\"question-description\">\n<p>You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:\u00a0<code>'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'<\/code>. The wheels can rotate freely and wrap around: for example we can turn\u00a0<code>'9'<\/code>\u00a0to be\u00a0<code>'0'<\/code>, or\u00a0<code>'0'<\/code>\u00a0to be\u00a0<code>'9'<\/code>. Each move consists of turning one wheel one slot.<\/p>\n<p>The lock initially starts at\u00a0<code>'0000'<\/code>, a string representing the state of the 4 wheels.<\/p>\n<p>You are given a list of\u00a0<code>deadends<\/code>\u00a0dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.<\/p>\n<p>Given a\u00a0<code>target<\/code>\u00a0representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"decode-attributes:false lang:default decode:true\">Input: deadends = [\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"], target = \"0202\"\r\nOutput: 6\r\nExplanation:\r\nA sequence of valid moves would be \"0000\" -&gt; \"1000\" -&gt; \"1100\" -&gt; \"1200\" -&gt; \"1201\" -&gt; \"1202\" -&gt; \"0202\".\r\nNote that a sequence like \"0000\" -&gt; \"0001\" -&gt; \"0002\" -&gt; \"0102\" -&gt; \"0202\" would be invalid,\r\nbecause the wheels of the lock become stuck after the display becomes the dead end \"0102\".\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"decode-attributes:false lang:default decode:true\">Input: deadends = [\"8888\"], target = \"0009\"\r\nOutput: 1\r\nExplanation:\r\nWe can turn the last wheel in reverse to move from \"0000\" -&gt; \"0009\".\r\n<\/pre>\n<p><b>Example 3:<\/b><\/p>\n<pre class=\"decode-attributes:false lang:default decode:true\">Input: deadends = [\"8887\",\"8889\",\"8878\",\"8898\",\"8788\",\"8988\",\"7888\",\"9888\"], target = \"8888\"\r\nOutput: -1\r\nExplanation:\r\nWe can't reach the target without getting stuck.\r\n<\/pre>\n<p><b>Example 4:<\/b><\/p>\n<pre class=\"\">Input: deadends = [\"0000\"], target = \"8888\"\r\nOutput: -1\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>The length of\u00a0<code>deadends<\/code>\u00a0will be in the range\u00a0<code>[1, 500]<\/code>.<\/li>\n<li><code>target<\/code>\u00a0will not be in the list\u00a0<code>deadends<\/code>.<\/li>\n<li>Every string in\u00a0<code>deadends<\/code>\u00a0and the string\u00a0<code>target<\/code>\u00a0will be a string of 4 digits from the 10,000 possibilities\u00a0<code>'0000'<\/code>\u00a0to\u00a0<code>'9999'<\/code>.<\/li>\n<\/ol>\n<p><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>\u9898\u76ee\u5927\u610f\uff1a<\/p>\n<p>\u7ed9\u4f60\u4e00\u4e2a4\u4f4d\u5bc6\u7801\u9501\uff0c0\u53ef\u4ee5\u8f6c\u52301\u548c9\uff0c1\u53ef\u4ee5\u8f6c\u52300\u548c2\uff0c\u3002\u3002\u3002\uff0c9\u53ef\u4ee5\u8f6c\u52300\u548c8\u3002<\/p>\n<p>\u53e6\u5916\u7ed9\u4f60\u4e00\u4e9b\u6b7b\u9501\u7684\u5bc6\u7801\uff0c\u6bd4\u59821234\uff0c\u4e00\u4f46\u8f6c\u5230\u4efb\u4f55\u4e00\u4e2a\u6b7b\u9501\u7684\u5bc6\u7801\uff0c\u9501\u5c31\u65e0\u6cd5\u518d\u8f6c\u52a8\u4e86\u3002<\/p>\n<p>\u7ed9\u4f60\u4e00\u4e2a\u76ee\u6807\u5bc6\u7801\uff0c\u95ee\u4f60\u6700\u5c11\u8981\u8f6c\u591a\u5c11\u6b21\u624d\u80fd\u4ece0000\u8f6c\u5230\u76ee\u6807\u5bc6\u7801\u3002<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 133 ms\r\nclass Solution {\r\npublic:\r\n  int openLock(vector&lt;string&gt;&amp; deadends, string target) {\r\n    const string start = \"0000\";\r\n    unordered_set&lt;string&gt; dead(deadends.begin(), deadends.end());\r\n    if (dead.count(start)) return -1;\r\n    if (start == target) return 0;\r\n    \r\n    queue&lt;string&gt; q;\r\n    unordered_set&lt;string&gt; visited{start};\r\n    \r\n    int steps = 0;\r\n    q.push(start);\r\n    while (!q.empty()) {\r\n      ++steps;\r\n      const int size = q.size();\r\n      for (int i = 0; i &lt; size; ++i) {\r\n        const string curr = q.front(); \r\n        q.pop();\r\n        for (int i = 0; i &lt; 4; ++i)\r\n          for (int j = -1; j &lt;= 1; j += 2) {\r\n            string next = curr;\r\n            next[i] = (next[i] - '0' + j + 10) % 10 + '0';\r\n            if (next == target) return steps;\r\n            if (dead.count(next) || visited.count(next)) continue; \r\n            q.push(next);\r\n            visited.insert(next);\r\n          }\r\n      }\r\n    }\r\n    \r\n    return -1;\r\n  }\r\n};<\/pre>\n<p>C++ \/ Bidirectional BFS<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 32 ms\r\nclass Solution {\r\npublic:\r\n  int openLock(vector&lt;string&gt;&amp; deadends, string target) {\r\n    const string start = \"0000\";\r\n    unordered_set&lt;string&gt; dead(deadends.begin(), deadends.end());\r\n    if (dead.count(start)) return -1;\r\n    if (target == start) return 0;\r\n    \r\n    queue&lt;string&gt; q1;\r\n    queue&lt;string&gt; q2;\r\n    unordered_set&lt;string&gt; v1{start};\r\n    unordered_set&lt;string&gt; v2{target};\r\n    \r\n    int s1 = 0;\r\n    int s2 = 0;\r\n    q1.push(start);\r\n    q2.push(target);\r\n    while (!q1.empty() &amp;&amp; !q2.empty()) {      \r\n      if (!q1.empty()) ++s1;\r\n      const int size = q1.size();\r\n      for (int i = 0; i &lt; size; ++i) {\r\n        const string curr = q1.front(); \r\n        q1.pop();\r\n        for (int i = 0; i &lt; 4; ++i)\r\n          for (int j = -1; j &lt;= 1; j += 2) {\r\n            string next = curr;\r\n            next[i] = (next[i] - '0' + j + 10) % 10 + '0';\r\n            if (v2.count(next)) return s1 + s2;\r\n            if (dead.count(next) || v1.count(next)) continue; \r\n            q1.push(next);\r\n            v1.insert(next);\r\n          }\r\n      }\r\n      swap(q1, q2);\r\n      swap(v1, v2);\r\n      swap(s1, s2);\r\n    }\r\n    \r\n    return -1;\r\n  }    \r\n};<\/pre>\n<p>C++ \/ Bidirectional BFS \/ int state \/ Array<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 9 ms\r\nclass Solution {\r\npublic:\r\n  int openLock(vector&lt;string&gt;&amp; deadends, string target) {\r\n    constexpr int kMaxN = 10000;\r\n    const vector&lt;int&gt; bases{1, 10, 100, 1000};\r\n    const int start = 0;\r\n    const int goal = stoi(target);\r\n    \r\n    queue&lt;int&gt; q1;\r\n    queue&lt;int&gt; q2;\r\n    vector&lt;int&gt; v1(kMaxN, 0);\r\n    vector&lt;int&gt; v2(kMaxN, 0);  \r\n    for (const string&amp; deadend : deadends)\r\n        v1[stoi(deadend)] = v2[stoi(deadend)] = -1;\r\n    \r\n    if (v1[start] == -1) return -1;\r\n    if (start == goal) return 0;\r\n    \r\n    v1[start] = 1;\r\n    v2[goal] = 1;\r\n    \r\n    int s1 = 0;\r\n    int s2 = 0;\r\n    q1.push(start);\r\n    q2.push(goal);\r\n    while (!q1.empty() &amp;&amp; !q2.empty()) {      \r\n      if (!q1.empty()) ++s1;\r\n      const int size = q1.size();\r\n      for (int i = 0; i &lt; size; ++i) {\r\n        const int curr = q1.front(); \r\n        q1.pop();\r\n        for (int i = 0; i &lt; 4; ++i) {\r\n          int r = (curr \/ bases[i]) % 10;\r\n          for (int j = -1; j &lt;= 1; j += 2) {\r\n            const int next = curr + ((r + j + 10) % 10 - r) * bases[i];\r\n            if (v2[next] == 1) return s1 + s2;\r\n            if (v1[next]) continue;            \r\n            q1.push(next);\r\n            v1[next] = 1;\r\n          }\r\n        }\r\n      }\r\n      swap(q1, q2);\r\n      swap(v1, v2);\r\n      swap(s1, s2);\r\n    }    \r\n    return -1;\r\n  }\r\n};<\/pre>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 132 ms\r\nclass Solution {\r\n  public int openLock(String[] deadends, String target) {\r\n    String start = \"0000\";\r\n    Set&lt;String&gt; dead = new HashSet();\r\n    for (String d: deadends) dead.add(d);\r\n    if (dead.contains(start)) return -1;\r\n\r\n    Queue&lt;String&gt; queue = new LinkedList();\r\n    queue.offer(start);        \r\n\r\n    Set&lt;String&gt; visited = new HashSet();\r\n    visited.add(start);\r\n\r\n    int steps = 0;\r\n    while (!queue.isEmpty()) {\r\n      ++steps;\r\n      int size = queue.size();\r\n      for (int s = 0; s &lt; size; ++s) {\r\n        String node = queue.poll();\r\n        for (int i = 0; i &lt; 4; ++i) {\r\n          for (int j = -1; j &lt;= 1; j += 2) {\r\n            char[] chars = node.toCharArray();\r\n            chars[i] = (char)(((chars[i] - '0') + j + 10) % 10 + '0');\r\n            String next = new String(chars);\r\n            if (next.equals(target)) return steps;\r\n            if (dead.contains(next) || visited.contains(next))\r\n                continue;\r\n            visited.add(next);\r\n            queue.offer(next);\r\n          }\r\n        }\r\n      }\r\n    }\r\n    return -1;\r\n  }\r\n}<\/pre>\n<p>Python<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRuntime: 955 ms\r\n\"\"\"\r\nclass Solution:\r\n    def openLock(self, deadends, target):\r\n        from collections import deque\r\n        deads = set(deadends)\r\n        start = '0000'\r\n        if start in deads: return -1\r\n        q = deque([(start, 0)])        \r\n        visited = set(start)        \r\n        while q:                \r\n            node, step = q.popleft()\r\n            for i in range(0, 4):\r\n                for j in [-1, 1]:\r\n                    nxt = node[:i] + str((int(node[i]) + j + 10) % 10) + node[i+1:]\r\n                    if nxt == target: return step + 1\r\n                    if nxt in deads or nxt in visited: continue\r\n                    q.append((nxt, step + 1))\r\n                    visited.add(nxt)\r\n        return -1\r\n<\/pre>\n<p>Python \/ Int state<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRuntime: 568 ms\r\n\"\"\"\r\nclass Solution:\r\n    def openLock(self, deadends, target):\r\n        from collections import deque\r\n        bases = [1, 10, 100, 1000]\r\n        deads = set(int(x) for x in deadends)\r\n        start, goal = int('0000'), int(target)        \r\n        if start in deads: return -1\r\n        if start == goal: return 0\r\n        q = deque([(start, 0)])\r\n        visited = set([start])\r\n        while q:   \r\n            node, step = q.popleft()\r\n            for i in range(0, 4):\r\n                r = (node \/\/ bases[i]) % 10\r\n                for j in [-1, 1]:\r\n                    nxt = node + ((r + j + 10) % 10 - r) * bases[i]\r\n                    if nxt == goal: return step + 1\r\n                    if nxt in deads or nxt in visited: continue\r\n                    q.append((nxt, step + 1))\r\n                    visited.add(nxt)\r\n        return -1\r\n<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem: You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:\u00a0&#8216;0&#8217;, &#8216;1&#8217;, &#8216;2&#8217;, &#8216;3&#8217;, &#8216;4&#8217;, &#8216;5&#8217;, &#8216;6&#8217;, &#8216;7&#8217;,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[165,44],"tags":[34,110,87],"class_list":["post-1324","post","type-post","status-publish","format-standard","hentry","category-hard","category-searching","tag-bfs","tag-bidirectional-bfs","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1324","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=1324"}],"version-history":[{"count":17,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1324\/revisions"}],"predecessor-version":[{"id":1402,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1324\/revisions\/1402"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1324"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1324"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1324"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}