{"id":317173,"date":"2021-02-04T20:40:04","date_gmt":"2021-02-04T12:40:04","guid":{"rendered":"http:\/\/4563.org\/?p=317173"},"modified":"2021-02-04T20:40:04","modified_gmt":"2021-02-04T12:40:04","slug":"%e5%88%b7%e4%b8%80%e5%a5%97%e4%ba%9a%e9%ba%bb%e9%9d%a2%e8%af%95%e7%9c%9f%e9%a2%98%ef%bc%9a%e5%8d%95%e8%af%8d%e6%8e%a5%e9%be%99-ii","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=317173","title":{"rendered":"\u5237\u4e00\u5957\u4e9a\u9ebb\u9762\u8bd5\u771f\u9898\uff1a\u5355\u8bcd\u63a5\u9f99 II"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  \u5237\u4e00\u5957\u4e9a\u9ebb\u9762\u8bd5\u771f\u9898\uff1a\u5355\u8bcd\u63a5\u9f99 II               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span>  <span><i><\/i> 6<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<h3>\u63cf\u8ff0<\/h3>\n<p>\u7ed9\u51fa\u4e24\u4e2a\u5355\u8bcd\uff08 start \u548c end \uff09\u548c\u4e00\u4e2a\u5b57\u5178\uff0c\u627e\u51fa\u6240\u6709\u4ece start \u5230 end \u7684\u6700\u77ed\u8f6c\u6362\u5e8f\u5217\u3002 \u53d8\u6362\u89c4\u5219\u5982\u4e0b\uff1a<\/p>\n<ol>\n<li>\u6bcf\u6b21\u53ea\u80fd\u6539\u53d8\u4e00\u4e2a\u5b57\u6bcd\u3002<\/li>\n<li>\u53d8\u6362\u8fc7\u7a0b\u4e2d\u7684\u4e2d\u95f4\u5355\u8bcd\u5fc5\u987b\u5728\u5b57\u5178\u4e2d\u51fa\u73b0\u3002<\/li>\n<\/ol>\n<p>\u6240\u6709\u5355\u8bcd\u5177\u6709\u76f8\u540c\u7684\u957f\u5ea6\u3002 \u6240\u6709\u5355\u8bcd\u90fd\u53ea\u5305\u542b\u5c0f\u5199\u5b57\u6bcd\u3002 \u9898\u76ee\u786e\u4fdd\u5b58\u5728\u5408\u6cd5\u7684\u8def\u5f84\u3002<\/p>\n<p>\u5728\u7ebf\u8bc4\u6d4b\u5730\u5740<\/p>\n<h3>\u6837\u4f8b 1<\/h3>\n<pre><code>\u8f93\u5165\uff1astart = \"a\"\uff0cend = \"c\"\uff0cdict =[\"a\",\"b\",\"c\"] \u8f93\u51fa\uff1a[[\"a\",\"c\"]] \u89e3\u91ca\uff1a \"a\"-&gt;\"c\" <\/code><\/pre>\n<h3>\u6837\u4f8b 2<\/h3>\n<pre><code>\u8f93\u5165\uff1astart =\"hit\"\uff0cend = \"cog\"\uff0cdict =[\"hot\",\"dot\",\"dog\",\"lot\",\"log\"] \u8f93\u51fa\uff1a[[\"hit\",\"hot\",\"dot\",\"dog\",\"cog\"],[\"hit\",\"hot\",\"lot\",\"log\",\"cog\"]] \u89e3\u91ca\uff1a 1.\"hit\"-&gt;\"hot\"-&gt;\"dot\"-&gt;\"dog\"-&gt;\"cog\" 2.\"hit\"-&gt;\"hot\"-&gt;\"lot\"-&gt;\"log\"-&gt;\"cog\" <\/code><\/pre>\n<p>\u4ece end \u5230 start \u505a\u4e00\u6b21 BFS\uff0c\u5e76\u4e14\u628a\u8ddd\u79bb end \u7684\u8ddd\u79bb\u90fd\u4fdd\u5b58\u5728 distance \u4e2d\u3002 \u7136\u540e\u5728\u4ece start \u5230 end \u505a\u4e00\u6b21 DFS\uff0c\u6bcf\u8d70\u4e00\u6b65\u5fc5\u987b\u786e\u4fdd\u79bb end \u7684 distance \u8d8a\u6765\u8d8a\u8fd1\u3002<\/p>\n<p>\u4e0e\u53e6\u5916\u4e00\u4e2a\u4ee3\u7801\u4e2d\u63d0\u524d\u5efa\u7acb index \u4e0d\u540c\uff0c\u8fd9\u91cc\u662f\u5728\u5bfb\u627e\u4e0b\u4e00\u4e2a\u53d8\u6362\u5355\u8bcd\u7684\u65f6\u5019\uff0c\u518d\u53bb\u83b7\u5f97\u5bf9\u5e94\u7684\u5355\u8bcd\u5217\u8868\u3002\u4e00\u4e2a\u5355\u8bcd\u6700\u591a\u6709 L \u4e2a\u5b57\u7b26\uff0c\u6bcf\u4e2a\u5b57\u7b26\u6709 25 \u79cd\u4e0d\u540c\u7684\u53d8\u5316\uff08 26 \u4e2a\u5b57\u6bcd\u9664\u6389\u8fd9\u4e2a\u4f4d\u7f6e\u4e0a\u7684\u5b57\u6bcd\uff09\uff0c\u7136\u540e check \u4e00\u4e0b\u5728\u4e0d\u5728 dict \u91cc\u5c31\u77e5\u9053\u662f\u4e0d\u662f next word \u4e86\u3002<\/p>\n<pre><code>from collections import deque  class Solution:     \"\"\"     @param: start: a string     @param: end: a string     @param: dict: a set of string     @return: a list of lists of string     \"\"\"     def findLadders(self, start, end, dict):         dict.add(start)         dict.add(end)         distance = {}                  self.bfs(end, distance, dict)                  results = []         self.dfs(start, end, distance, dict, [start], results)                  return results      def bfs(self, start, distance, dict):         distance[start] = 0         queue = deque([start])         while queue:             word = queue.popleft()             for next_word in self.get_next_words(word, dict):                 if next_word not in distance:                     distance[next_word] = distance[word] + 1                     queue.append(next_word)          def get_next_words(self, word, dict):         words = []         for i in range(len(word)):             for c in 'abcdefghijklmnopqrstuvwxyz':                 next_word = word[:i] + c + word[i + 1:]                 if next_word != word and next_word in dict:                     words.append(next_word)         return words                              def dfs(self, curt, target, distance, dict, path, results):         if curt == target:             results.append(list(path))             return                  for word in self.get_next_words(curt, dict):             if distance[word] != distance[curt] - 1:                 continue             path.append(word)             self.dfs(word, target, distance, dict, path, results)             path.pop() <\/code><\/pre>\n<p>\u66f4\u591a\u9898\u89e3\u53c2\u8003<\/p>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>0<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>\u5237\u4e00\u5957\u4e9a\u9ebb\u9762\u8bd5\u771f\u9898\uff1a\u5355\u8bcd\u63a5\u9f99 II&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/317173"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=317173"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/317173\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=317173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=317173"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=317173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}