{"id":137001,"date":"2020-07-22T04:21:54","date_gmt":"2020-07-21T20:21:54","guid":{"rendered":"http:\/\/4563.org\/?p=137001"},"modified":"2020-07-22T04:21:54","modified_gmt":"2020-07-21T20:21:54","slug":"%e4%ba%9a%e9%a9%ac%e9%80%8a%e9%9d%a2%e8%af%95%e9%ab%98%e9%a2%91%e9%a2%98%ef%bc%9a%e5%8d%95%e8%af%8d%e6%8e%a5%e9%be%99%e2%85%a1","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=137001","title":{"rendered":"\u4e9a\u9a6c\u900a\u9762\u8bd5\u9ad8\u9891\u9898\uff1a\u5355\u8bcd\u63a5\u9f99\u2161"},"content":{"rendered":"
\n
\n
\n

\u4e9a\u9a6c\u900a\u9762\u8bd5\u9ad8\u9891\u9898\uff1a\u5355\u8bcd\u63a5\u9f99\u2161 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : hakunamatata11 <\/span> <\/i> 6<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u7ed9\u51fa\u4e24\u4e2a\u5355\u8bcd\uff08start<\/em>\u548cend<\/em>\uff09\u548c\u4e00\u4e2a\u5b57\u5178\uff0c\u627e\u51fa\u6240\u6709\u4ecestart<\/em>\u5230end<\/em>\u7684\u6700\u77ed\u8f6c\u6362\u5e8f\u5217\u3002<\/p>\n

\u53d8\u6362\u89c4\u5219\u5982\u4e0b\uff1a<\/p>\n

    \n
  1. \u6bcf\u6b21\u53ea\u80fd\u6539\u53d8\u4e00\u4e2a\u5b57\u6bcd\u3002<\/li>\n
  2. \u53d8\u6362\u8fc7\u7a0b\u4e2d\u7684\u4e2d\u95f4\u5355\u8bcd\u5fc5\u987b\u5728\u5b57\u5178\u4e2d\u51fa\u73b0\u3002<\/li>\n<\/ol>\n

    ps<\/p>\n

      \n
    1. \u6240\u6709\u5355\u8bcd\u5177\u6709\u76f8\u540c\u7684\u957f\u5ea6\u3002<\/li>\n
    2. \u6240\u6709\u5355\u8bcd\u90fd\u53ea\u5305\u542b\u5c0f\u5199\u5b57\u6bcd\u3002<\/li>\n
    3. \u9898\u76ee\u786e\u4fdd\u5b58\u5728\u5408\u6cd5\u7684\u8def\u5f84\u3002<\/li>\n<\/ol>\n

      \u6837\u4f8b 1:<\/p>\n

      \u8f93\u5165\uff1astart = \"a\"\uff0cend = \"c\"\uff0cdict =[\"a\",\"b\",\"c\"] \u8f93\u51fa\uff1a[[\"a\",\"c\"]] \u89e3\u91ca\uff1a \"a\"->\"c\" <\/code><\/pre>\n
      \u6837\u4f8b 2:<\/p>\n
      \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\"->\"hot\"->\"dot\"->\"dog\"->\"cog\" 2.\"hit\"->\"hot\"->\"lot\"->\"log\"->\"cog\" \u7b2c\u4e00\u4e2a\u5e8f\u5217\u7684\u5b57\u5178\u5e8f\u5c0f\u4e8e\u7b2c\u4e8c\u4e2a\u3002 <\/code><\/pre>\n
      ** [\u9898\u89e3] **<\/p>\n
      \u7b97\u6cd5\uff1aBFS+DFS<\/strong><\/p>\n
      \u9898\u76ee\u8981\u6c42\u627e\u51fa\u6240\u6709\u4ecestart<\/em>\u5230end<\/em>\u7684\u6700\u77ed\u8f6c\u6362\u5e8f\u5217\uff0c\u663e\u7136\u6211\u4eec\u9700\u8981\u8003\u8651bfs<\/code>\u641c\u7d22\u6700\u77ed\u8def\uff0c\u8def\u5f84\u4e2d\u7684\u4e0b\u4e00\u8df3\u90fd\u5b58\u5728\u4e8e\u5b57\u5178\u5185\uff0c\u7531\u4e8e\u90fd\u662f\u5c0f\u5199\u5b57\u6bcd\uff0c\u53ef\u4ee5\u679a\u4e3e\u5f53\u524d\u5b57\u7b26\u4e32\u4e0b\u4e00\u8df3\u53ef\u80fd\u7684\u6240\u6709\u5b57\u7b26\u4e32,\u5bf9\u4e8e\u5b57\u7b26\u4e32s<\/code>,\u5c06\u4ed6\u7684\u6bcf\u4e00\u4f4d\u90fd\u7528’a’-‘z’\u66ff\u6362\u4e00\u904d\uff0c\u5224\u65ad\u88ab\u66ff\u6362\u5b57\u6bcd\u540e\u7684s<\/code>\u662f\u5426\u5b58\u5728\u4e8edict<\/code>\u4e2d,\u8fd9\u6837\u76f8\u6bd4\u76f4\u63a5\u5728dict<\/code>\u4e2d\u641c\u7d22\u4e0b\u4e00\u8df3\u53ef\u4ee5\u6709\u6548\u7684\u51cf\u5c11\u65f6\u95f4\u590d\u6742\u5ea6\uff08\u5982\u679c\u76f4\u63a5\u627e\u4e0b\u4e00\u8df3\u90a3\u4e48\u5fc5\u987b\u904d\u5386dict<\/code>\uff09\u3002\u8dd1\u5b8c\u6240\u6709\u6700\u77ed\u8def\u5f84\u540e\u518d dfs \u5c06\u56fe\u8f6c\u6362\u4e3astart--end<\/code>\u7684\u8def\u5f84<\/p>\n
        \n
      • \u5148\u6dfb\u52a0end<\/code>\u5230dict<\/code>\u4e2d\uff0c\u4fbf\u4e8e\u8ba1\u7b97<\/li>\n
      • \u5148\u5bf9start--end<\/code>\u901a\u8fc7\u961f\u5217bfs<\/code>\u8ba1\u7b97\u51fa\u6240\u6709\u6700\u77ed\u8def<\/li>\n
      • \u5bf9\u4e8e\u6bcf\u4e2a\u5f53\u524d\u5b57\u7b26\u4e32\u7528\u66b4\u529b\u66ff\u6362\u6bcf\u4e00\u4f4d\u7684\u5b57\u6bcd\uff0c\u67e5\u627e\u662f\u5426\u5b58\u5728\u4e8edict<\/code>\u4e2d<\/li>\n
      • \u901a\u8fc7dfs<\/code>\u904d\u5386\u6240\u6709\u6700\u77ed\u8def\uff0c\u6253\u5370\u51fa\u6240\u6709\u8def\u5f84<\/li>\n<\/ul>\n
        \u590d\u6742\u5ea6\u5206\u6790<\/strong><\/p>\n
          \n
        • \n
          \u65f6\u95f4\u590d\u6742\u5ea6O((V+E))<\/code><\/p>\n<\/li>\n
        • \n
          bfs\u00a0O(V+E)<\/code>\u904d\u5386\u6240\u6709\u8fb9\u00a0E<\/code>\uff08\u5373\u5f53\u524d\u5b57\u7b26\u4e32\u7684\u4e0b\u4e00\u8df3\uff09\u548c\u70b9V<\/code>\uff0cdfsO(size(dict))<\/code>\u8dd1\u6700\u540e\u7684\u6700\u77ed\u8def<\/p>\n<\/li>\n
        • \n
          \u7a7a\u95f4\u590d\u6742\u5ea6O(size(dict)*k)<\/code><\/p>\n<\/li>\n
        • \n
          \u5b58\u6bcf\u4e2a\u5b57\u7b26\u4e32\u4e0e\u4e0b\u4e00\u8df3\u5b57\u7b26\u4e32\u7684\u96c6\u5408\u4ee5\u53ca\u6700\u77ed\u8def\u5f84<\/p>\n<\/li>\n<\/ul>\n
          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):         from collections import defaultdict         dict = set(dict)         #\u5c06 end \u6dfb\u52a0\u8fdb dict,\u9632\u6b62\u7ed3\u679c\u4e3a[]         dict.add(end)         res = []         # \u8bb0\u5f55\u5355\u8bcd\u4e0b\u4e00\u6b65\u80fd\u8f6c\u5230\u7684\u5355\u8bcd         next_word_dict = defaultdict(list)         # \u8bb0\u5f55\u5230 start \u8ddd\u79bb         distance = {}         distance[start] = 0          # \u66b4\u529b\u5339\u914d,\u5f53\u524d\u5b57\u7b26\u4e32\u4fee\u6539\u4e00\u4e2a\u5b57\u6bcd\u540e\u7684\u65b0\u5b57\u7b26\u4e32\u5b58\u5728\u4e8e dict \u4e2d         def next_word(word):             ans = []             for i in range(len(word)):                        #97=ord('a')\uff0c123=ord('z')+1                   for j in range(97, 123):                     tmp = word[:i] + chr(j) + word[i + 1:]                     if tmp != word and tmp in dict:                         ans.append(tmp)             return ans         # \u6c42\u5230 start \u7684\u8ddd\u79bb         def bfs():             q = collections.deque()             q.append(start)             step = 0             flag = False #\u6807\u8bb0\u662f\u5426\u627e\u5230\u7ed3\u679c             while len(q) is not 0:                 step += 1                 n=len(q)                 for i in range(n):                     word=q[0]                     q.popleft()                     for nextword in next_word(word):                         next_word_dict[word].append(nextword)                        #\u5f53\u4e0b\u4e00\u8df3\u662f end \u65f6\uff0c\u5c31\u53ef\u4ee5\u7ed3\u675f\u641c\u7d22                         if nextword == end:                             flag = True                         #\u5982\u679c\u6ca1\u88ab\u6dfb\u52a0\u8fc7\uff0c\u5219\u8fdb\u884c\u6dfb\u52a0                         if nextword not in distance:                             distance[nextword] = step                             q.append(nextword)                 if flag:                     break         # \u904d\u5386\u6240\u6709\u4ece start \u5230 end \u7684\u8def\u5f84         def dfs(tmp, step):             if tmp[-1] == end:                 res.append(tmp)                 return             for word in next_word_dict[tmp[-1]]:                 if distance[word] == step + 1:                     dfs(tmp + [word], step + 1)         #bfs \u641c start--end \u7684\u6700\u77ed\u8def\u5f84                    bfs()         #dfs \u8f93\u51fa\u8ddd\u79bb\u6700\u77ed\u7684\u8def\u5f84         dfs([start], 0)         return res <\/code><\/pre>\n
          \u672c\u5468\u516d\u8fd8\u6709\u7cfb\u7edf\u8bbe\u8ba1\u514d\u8d39\u8bb2\u5ea7\u5662~<\/h2>\n
          2 \u5c0f\u65f6\u5e26\u4f60\u8bbe\u8ba1\u9ad8\u9891\u7cfb\u7edf\u8bbe\u8ba1\u9762\u8bd5\u9898\u2014\u2014\u79d2\u6740\u7cfb\u7edf\uff0c\u5168\u9762\u89e3\u6790\u9ad8\u5e76\u53d1\u5e38\u89c1\u95ee\u9898\u3002 \u6233\u6211\u514d\u8d39\u62a5\u540d<\/p>\n
          \u5185\u5bb9\u4ecb\u7ecd\uff1a<\/h2>\n
          \u901a\u8fc7\u79d2\u6740\u7cfb\u7edf\u548c\u8ba2\u7968\u7cfb\u7edf\u4e86\u89e3\u5982\u4e0b\u5185\u5bb9\uff1a<\/p>\n
            \n
          • \u9ad8\u5e76\u53d1\u573a\u666f\u4e0b\u5f15\u53d1\u7684\u5e38\u89c1\u95ee\u9898<\/li>\n
          • \u4e86\u89e3\u6570\u636e\u4e00\u81f4\u6027<\/li>\n
          • \u4ec0\u4e48\u662f\u52a8\u9759\u5206\u79bb<\/li>\n
          • \u8bfb\u5199\u5206\u79bb\u5982\u4f55\u5b9e\u73b0<\/li>\n
          • \u5982\u4f55\u9632\u6b62\u8d85\u5356<\/li>\n<\/ul>\n
            \u8bb2\u5e08\u4ecb\u7ecd<\/h2>\n
            \u5357\u5e1d\u2014\u2014\u963f\u91cc\u5728\u804c P7+\uff0c14 \u5e74+\u8f6f\u4ef6\u5f00\u53d1\u7ecf\u9a8c\uff0c10 \u5e74+\u67b6\u6784\u8bbe\u8ba1\u7ecf\u9a8c\uff0c\u64c5\u957f\u7cfb\u7edf\u6574\u4f53\u67b6\u6784\u65b9\u6848\u8bbe\u8ba1\uff0c\u9762\u8bd5\u8fc7\u8d85\u8fc7 100+\u5019\u9009\u4eba\uff0c\u62e5\u6709\u591a\u5e74\u8d44\u6df1\u9762\u8bd5\u5b98\u7ecf\u9a8c\u3002<\/p>\n
            \u8bb2\u5ea7\u65f6\u95f4\uff1a2020\/7\/18 \u672c\u5468\u516d \u4e0a\u5348 9:30:00<\/h2>\n
            \u8bfe\u7a0b\u65f6\u957f: 120 \u5206\u949f<\/p>\n
            \u6233\u6211\u514d\u8d39\u62a5\u540d<\/p>\n<\/p><\/div>\n
             \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (1<\/span>)        <\/div>\n
             <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
              \n
            • \n
              \n
              \n
               \u8cc7\u6df1\u5927\u4f6c : BiteTheDust <\/span>  <\/div>\n
               <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                           \u8fd9\u79cd\u5f88\u660e\u663e\u7684\u9690\u5f0f\u56fe\u8f6c\u6362\u6ca1\u5565\u82b1\u5934\u5566                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
            • \n","protected":false},"excerpt":{"rendered":"
              \u4e9a\u9a6c\u900a\u9762\u8bd5\u9ad8\u9891\u9898\uff1a\u5355\u8bcd\u63a5\u9f99\u2161 \u8cc7\u6df1…<\/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\/137001"}],"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=137001"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/137001\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=137001"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=137001"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=137001"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}